Learning Binarized Graph Representations with Multi-faceted Quantization Reinforcement for Top-K Recommendation

We propose the graph layer-wise quantization mainly by computing quantized embeddings and embedding scalers: (1) these quantized embeddings sketch the full-precision embeddings with $d$-dimensional binarized codes (i.e., $\{-1,1\}^{d}$); and (2) each embedding scaler reveals the value range of original embedding entries. Specifically, during the graph convolution at each layer, we track the intermediate information (e.g., $\boldsymbol{v}^{(l)}_{u}$) and perform the layer-wise 1-bit quantization in parallel as:

where embedding segments $\boldsymbol{q}_{u}^{(l)}$, $\boldsymbol{q}_{i}^{(l)}$ $\in$ $\{-1,1\}^{d}$ retain the node latent features directly from $\boldsymbol{v}^{(l)}_{u}$ and $\boldsymbol{v}^{(l)}_{i}$. To equip with the layer-wise quantized embeddings, we further include a layer-wise positive embedding scaler for each node (e.g., $\alpha_{u}^{(l)}$ $\in$ $\mathbb{R}^{+}$), such that $\boldsymbol{v}^{(l)}_{u}$ $\doteq$ $\alpha_{u}^{(l)}$$\boldsymbol{q}^{(l)}_{u}$. Then for each entry in $\alpha_{u}^{(l)}$$\boldsymbol{q}^{(l)}_{u}$, it is still binarized by $\{-\alpha_{u}^{(l)}$, $\alpha_{u}^{(l)}\}$. In this work, we compute the mean of L1-norm as:

Instead of setting $\alpha_{u}^{(l)}$ and $\alpha_{i}^{(l)}$ as learnable, such deterministic computation is simple yet effective to provide the scaling functionality whilst substantially pruning the parameter search space. The experimental demonstration is in Appendix F.2.

After $L$ layers of quantization and scaling, we have built the following binarized embedding table for each graph node $x$ as:

From the technical perspective, BiGeaR binarizes the intermediate semantics at different layers of the receptive field (Veličković et al., 2018; Wu et al., 2020) for each node. This, essentially, achieves the magnification effect of feature uniqueness to enrich user-item representations via the interaction graph exploration. We leave the analysis in § 3.1.

Model Prediction. Based on the learned embedding table, we predict the matching scores by adopting the inner product:

where function $f(\cdot,\cdot)$ in this work is implemented as:

Here $\big{|}\big{|}$ represents concatenation of binarized embedding segments, in which weight $w_{l}$ measures the contribution of each segment in prediction. $w_{l}$ can be defined as a hyper-parameter or a learnable variable (e.g., with attention mechanism (Veličković et al., 2018)). In this work, we set $w_{l}$ $\propto$ $l$ to linearly increase $w_{l}$ for segments from lower-layers to higher-layers, mainly for its computational simplicity and stability.

Computation Acceleration. Notice that for each segment of $f(\mathcal{A}_{u},\mathcal{Q}_{u})$, e.g., $w_{l}\alpha_{u}^{(l)}\boldsymbol{q}^{(l)}_{u}$, entries are binarized by two values (i.e., $-w_{l}\alpha_{u}^{(l)}$ or $w_{l}\alpha_{u}^{(l)}$). Thus, we can achieve the prediction acceleration by decomposing Equation (5) with bitwise operations. Concretely, in practice, $\boldsymbol{q}^{(l)}_{u}$ and $\boldsymbol{q}^{(l)}_{i}$ will be firstly encoded into basic $d$-bits binary codes, denoted by $\boldsymbol{{\ddot{q}}}^{(l)}_{u},\boldsymbol{{\ddot{q}}}^{(l)}_{i}\in\{0,1\}^{d}$. Then we replace Equation (5) by introducing the following formula:

Compared to the original computation approach in Equation (5), our bitwise-operation-supported prediction in Equation (7) reduces the number of floating-point operations (#FLOP) with Popcount and XNOR. We illustrate an example in Figure 2(b).

To alleviate the asymmetric inference capability issue between full-precision representations and binarized ones, we introduce the self-supervised inference distillation such that binarized embeddings can well inherit the inference knowledge from full-precision ones. Generally, we treat our full-precision intermediate embeddings (e.g., $\boldsymbol{v}_{u}^{(l)}$) as the teacher embeddings and the quantized segments as the student embeddings. Given both teacher and student embeddings, we can obtain their prediction scores as $\widehat{{y}}_{u,i}^{tch}$ and $\widehat{{y}}_{u,i}^{std}$. For Top-K recommendation, then our target is to reduce their discrepancy as:

A straightforward implementation of function $\mathcal{D}$ from the conventional knowledge distillation (Hinton et al., 2015; Anil et al., 2018) is to minimize their Kullback-Leibler divergence (KLD) or mean squared error (MSE). Despite their effectiveness in classification tasks (e.g., visual recognition (Anil et al., 2018; Xie et al., 2020)), they may not be appropriate for Top-K recommendation as:

• •

  Firstly, both KLD and MSE in $\mathcal{D}$ encourage the student logits (e.g., $\widehat{{y}}_{u,i}^{std}$) to be similarly distributed with the teacher logits in a macro view. But for ranking tasks, they may not well learn the relative order of user preferences towards items, which, however, is the key to improving Top-K recommendation capability.

• •

  Secondly, they both develop the distillation over the whole item corpus, which may be computational excessive for realistic model training. As the item popularity usually follows the Long-tail distribution (Park and Tuzhilin, 2008; Tang and Wang, 2018), learning the relative order of those frequently interacted items located at the tops of ranking lists actually contributes more to the Top-K recommendation performance.

To develop effective inference distillation, we propose to extract additional pseudo-positive training samples from teacher embeddings to regularize the targeted embeddings on each convolutional layer. Concretely, let $\sigma$ represent the activation function (e.g., Sigmoid). We first pre-train the teacher embeddings to minimize the Bayesian Personalized Ranking (BPR) loss (Rendle et al., 2012):

where $\mathcal{L}^{tch}_{BPR}$ forces the prediction of an observed interaction to be higher than its unobserved counterparts, and the teacher score $\widehat{y}^{\,tch}_{u,i}$ is computed as $\widehat{y}^{\,tch}_{u,i}=\big{<}\big{|}\big{|}_{l=0}^{L}w_{l}\boldsymbol{v}_{u}^{(l)},\big{|}\big{|}_{l=0}^{L}w_{l}\boldsymbol{v}_{i}^{(l)}\big{>}$. Please notice that we only disable binarization and its associated gradient estimation in pre-training. After it is well-trained, for each user $u$, we retrieve the layer-wise teacher inference towards all items $\mathcal{I}$:

Based on the segment scores $\boldsymbol{\widehat{y}}_{u}^{\,tch,(l)}$ at the $l$-th layer, we first sort out Top-R items with the highest matching scores, denoted by $S^{(l)}_{tch}(u)$. And hyper-parameter R $\ll$ $\mathcal{I}$. Inspired by (Tang and Wang, 2018), then we propose our layer-wise inference distillation as follows:

where student scores $\widehat{\boldsymbol{y}}^{\,std,(l)}_{u}$ is computed similarly to Equation (10) and $S^{(l)}_{tch}(u,k)$ returns the $k$-th high-scored item from the pseudo-positive samples. $w_{k}$ is the ranking-aware weight presenting two major effects: (1) since samples in $S^{(l)}_{tch}(u)$ are not necessarily all ground-truth positive, $w_{k}$ thus balances their contribution to the overall loss; (2) it dynamically adjusts the weight importance for different ranking positions in $S^{(l)}_{tch}(u)$. To achieve these, $w_{k}$ can be developed by following the parameterized geometric distribution for approximating the tailed item popularity (Rendle and Freudenthaler, 2014):

where $\lambda_{1}$ and $\lambda_{2}$ control the loss contribution level and sharpness of the distribution. Intuitively, $\mathcal{L}_{ID}$ encourages highly-recommended items from full-precision embeddings to more frequently appear in the student’s inference list. Moreover, our distillation approach regularizes the embedding quantization in a layer-wise manner as well; this will effectively narrow their inference discrepancy for a more correlated recommendation capability.

Objective Function. Combining $\mathcal{L}^{std}_{BPR}$ that calculates BPR loss (similar to Equation (9)) with the student predictions from Equation (5) and $\mathcal{L}_{ID}$ for all training samples, our final objective function for learning embedding binarization is defined as:

where $||\Theta||_{2}^{2}$ is the $L$2-regularizer of node embeddings parameterized by hyper-parameter $\lambda$ to avoid over-fitting.

Although Straight-Through Estimator (STE) (Bengio et al., 2013) enables an executable gradient flow for backpropagation, it however may cause the issue of inconsistent optimization direction in forward and backward propagation: as the integral of the constant 1 in STE is a linear function, other than $\operatorname{sign}(\cdot)$ function. To furnish more accurate gradient estimation, in this paper, we utilize the approximation of Dirac delta function (Bracewell and Bracewell, 1986) for gradient estimation.

Concretely, let $u(\phi)$ denote the unit-step function, a.k.a., Heaviside step function (function, 2022), where $u(\phi)$ $=$ $1$ for $\phi$ $>$ $0$ and $u(\phi)$ $=$ $0$ otherwise. Obviously, we can take a translation from step function to $\operatorname{sign}(\cdot)$ by $\operatorname{sign}(\phi)$ $=$ 2$u(\phi)$ - 1, and thus theoretically $\frac{\partial\operatorname{sign}(\phi)}{\partial\phi}$ $=$ $2\frac{\partial u(\phi)}{\partial\phi}$. As for $\frac{\partial u(\phi)}{\partial\phi}$, it has been proved (Bracewell and Bracewell, 1986) that, $\frac{\partial u(\phi)}{\partial\phi}$ $=$ $0$ if $\phi$ $\neq$ $0$, and $\frac{\partial u(\phi)}{\partial\phi}$ $=$ $\infty$ otherwise, which exactly is the Dirac delta function, a.k.a., the unit impulse function $\delta(\cdot)$ (Bracewell and Bracewell, 1986) shown in Figure 3(a). However, it is still intractable to directly use $\delta(\cdot)$ for gradient estimation. A feasible solution is to approximate $\delta(\cdot)$ by introducing zero-centered Gaussian probability density as follows:

which imlies that:

As shown in Figure 3(b)-(c), hyper-parameter $\gamma$ determines the sharpness of the derivative curve for approximation to $\operatorname{sign}(\cdot)$.

Intuitively, our proposed gradient estimator follows the main direction of factual gradients with $\operatorname{sign}(\cdot)$ in model optimization. This will produce a coordinated value quantization from continuous embeddings to quantized ones, and thus a series of evolving gradients can be estimated for the inputs with diverse value ranges. As we will show in § 4.6 of experiments, our gradient estimator can work better than other recent estimators (Gong et al., 2019; Qin et al., 2020; Darabi et al., 2018; Yang et al., 2019; Liu et al., 2019).

We take user $u$ as an example for illustration and the following analysis can be popularized to other nodes without loss of generality. Similar to sensitivity analysis in statistics (Koh and Liang, 2017) and influence diffusion in social networks (Xu et al., 2018), we measure how the latent feature of a distant node $x$ finally affects $u$’s representation segments before binarization (e.g., $\boldsymbol{v}^{(l)}_{u}$), supposing $x$ is a multi-hop neighbor of $u$. We denote the feature enrichment ratio $\mathbb{E}_{x\rightarrow u}^{(l)}$ as the L1-norm of Jacobian matrix $\begin{matrix}\left[{\partial\boldsymbol{v}^{(l)}_{u}}/\ {\partial\boldsymbol{v}^{(0)}_{x_{u}}}\right]\end{matrix}$, by detecting the absolute influence of all fluctuation in entries of $\boldsymbol{v}^{(0)}_{x}$ to $\boldsymbol{v}^{(l)}_{u}$, i.e., $\mathbb{E}_{x\rightarrow u}^{(l)}$ = $\begin{matrix}\left|\left|\left[{\partial\boldsymbol{v}^{(l)}_{u}}/\ {\partial\boldsymbol{v}^{(0)}_{x}}\right]\right|\right|_{1}\end{matrix}$. Focusing on a $l$-length path $h$ connected by the node sequence: $x_{h}^{l}$, $x_{h}^{l-1}$, $\cdots$, $x_{h}^{1}$, $x_{h}^{0}$, where $x_{h}^{l}$ = $u$ and $x_{h}^{0}$ = $x$, we follow the chain rule to develop the derivative decomposition as:

where $H$ is the number of paths between $u$ and $x$ in total. Since all factors in the computation chain are positive, then:

Note that here the term $\sum_{h=1}^{H}\prod_{k=1}^{l}1/|\mathcal{N}(x^{k}_{h})|$ is exactly the probability of the $l$-length random walk starting at $u$ that finally arrives at $x$, which can be interpreted as:

Magnification Effect of Feature Uniqueness. Equation (18) implies that, with the equal probability to visit adjacent neighbors, distant nodes with fewer degrees (i.e., $|\mathcal{N}(x)|$) will contribute more feature influence to user $u$. But most importantly, in practice, these $l$-hop neighbors of user $u$ usually represent certain esoteric and unique objects with less popularity. By collecting the intermediate information in different depth of the graph convolution, we can achieve the feature magnification effect for all unique nodes that live within $L$ hops of graph exploration, which finally enrich $u$’s semantics in all embedding segments for quantization.

To discuss the feasibility for realistic deployment, we compare BiGeaR with the best full-precision model LightGCN (He et al., 2020), as they are end-to-end with offline model training and online prediction.

Training Time Complexity. $M$, $N$, and $E$ represent the number of users, items, and edges; $S$ and $B$ are the epoch number and batch size. We use BiGeaR_tch and BiGeaR_std to denote the pre-training version and binarized one, respectively. As we can observe from Table 1, (1) both BiGeaR_tch and BiGeaR_std takes asymptotically similar complexity of graph convolution with LightGCN (where BiGeaR_std takes additional $O(2Sd(L+1)E)$ complexity for binarization). (2) For $\mathcal{L}_{BPR}$ computation, to prevent over-smoothing issue (Li et al., 2019; Li et al., 2018), usually $L\leq 4$; compare to the convolution operation, the complexity of $\mathcal{L}_{BPR}$ is acceptable. (3) For $\mathcal{L}_{ID}$ preparation, after the training of BiGeaR_tch, we firstly obtain the layer-wise prediction scores with $O(MNd(L+1))$ time complexity and then sort out the Top-R pseudo-positive samples for each user with $O(N+R\ln R)$. For BiGeaR_std, it takes a layer-wise inference distillation from BiGeaR_tch with $O\big{(}SRd(L+1)E\big{)}$. (4) To estimate the gradients for BiGeaR_std, it takes $O(2Sd(L+1)E)$ for all training samples.

Memory overhead and Prediction Acceleration. We measure the memory footprint of embedding tables for online prediction. As we can observe from the results in Table 2: (1) Theoretically, the embedding size ratio of our model over LightGCN is $\frac{32d}{(L+1)(32+d)}$. Normally, $L\leq 4$ and $d\geq 64$, thus our model achieves at least 4$\times$ space cost compression. (2) As for the prediction time cost, we compare the number of binary operations (#BOP) and floating-point operations (#FLOP) between our model and LightGCN. We find that BiGeaR replaces most of floating-point arithmetics (e.g., multiplication) with bitwise operations.

We exclude early quantization-based recommendation baselines, e.g., CH (Liu et al., 2014), DiscreteCF (Zhang et al., 2016), DPR (Zhang et al., 2017), and full-precision solutions, e.g., GC-MC (Berg et al., 2017), PinSage (Ying et al., 2018), mainly because the above competing models (Kang and McAuley, 2019; He et al., 2020; Wang et al., 2019; He et al., 2017) have validated the superiority.

We evaluate Top-K recommendation by varying K in {20, 40, 60, 80, 100}. We summarize the Top@20 results in Table 4 for detailed comparison and plot the Top-K recommendation curves in Appendix F.1. From Table 4, we have the following observations:

• •

  Our model offers a competitive recommendation capability to state-of-the-art full-precision recommender models. (1) BiGeaR generally outperforms most of full-precision recommender models excluding LightGCN over five benchmarks. The main reason is that our model and LightGCN take similar graph convolution methodology with network simplification (He et al., 2020), e.g., removing self-connection and feature transformation, which is proved to be effective for Top-K ranking and recommendation. Moreover, BiGeaR collects the different levels of interactive information in multi depths of graph exploration, which significantly enriches semantics to user-item representations for binarization. (2) Compared to the state-of-the-art method LightGCN, our model develops about 95%$\sim$102% of performance capability w.r.t. Recall@20 and NDCG@20 throughout all datasets. This shows that our proposed model designs are effective to narrow the performance gap with full-precision model LightGCN. Although the binarized embeddings learned by BiGeaR may not achieve the exact expressivity parity with the full-precision ones learned by LightGCN, considering the advantages of space compression and inference acceleration that we will present later, we argue that such performance capability is acceptable, especially for those resource-limited deployment scenarios.

• •

  Compared to all binarization-based recommender models, BiGeaR presents the empirically remarkable and statistically significant performance improvement. (1) Two conventional methods (LSH, HashNet) for general item retrieval tasks underperform CIGAR, HashGNN and BiGeaR, showing that a direct model adaptation may be too trivial for Top-K recommendation. (2) Compared to CIGAR, graph-based models generally work better. This is mainly because, CIGAR combines general neural networks with learning to hash techniques for fast candidate generation; on the contrary, graph-based models are more capable of exploring multi-hop interaction subgraphs to directly simulate the high-order collaborative filtering process for model learning. (3) Our model further outperforms HashGNN by about 26%$\sim$40% and 22%$\sim$40% w.r.t. Recall@20 and NDCG@20, proving the effectiveness of our proposed multi-faceted optimization components in embedding binarization. (4) Moreover, the significance test in which $p$-value $<$ 0.05 indicates that the improvements over all five benchmarks are statistically significant.

We analyze the resource consumption in training, online inference, and memory footprint by comparing to the best two competing models, i.e., LightGCN and HashGNN. Due to the page limits, we report the empirical results of MovieLens dataset in Table 5.

1. (1)

   $T_{train}$: we set batch size $B=2048$ and dimension size $d=256$ for all models. We find that HashGNN is fairly time-consuming than LightGCN and BiGeaR. This is because HashGNN adopts the early GCN framework (Hamilton et al., 2017) as the backbone; LightGCN and BiGeaR utilize more simplified graph convolution architecture in which operations such as self-connection, feature transformation, and nonlinear activation are all removed (He et al., 2020). Furthermore, BiGeaR needs 5.1s and 6.2s per epoch for pretraining and quantization, both of which take slightly more yet asymptotically similar time cost with LightGCN, basically following the complexity analysis in § 3.2.

2. (2)

   $T_{infer}$: we randomly generate 1,000 queries for online prediction and conduct experiments with the vanilla NumPy⁷⁷7https://www.lfd.uci.edu/~gohlke/pythonlibs/ on CPUs. We observe that HashGNN_s takes a similar time cost with LightGCN. This is because, while HashGNN_h purely binarizes the continuous embeddings, its relaxed version HashGNN_s adopts a Bernoulli random variable to provide the probability of replacing the quantized digits with original real values (Tan et al., 2020). Thus, although HashGNN_h can use Hamming distance for prediction acceleration, HashGNN_s with the improved recommendation accuracy can only be computed by floating-point arithmetics. As for BiGeaR, thanks to its bitwise-operation-supported capability, it runs about 8$\times$ faster than LightGCN whilst maintaining the similar performance on MovieLens dataset.

3. (3)

   $S_{ET}$: we only store the embedding tables that are necessary for online inference. As we just explain, HashGNN_s interprets embeddings by randomly selected real values, which, however, leads to the expansion of space consumption. In contrast to HashGNN_s, BiGeaR can separately store the binarized embeddings and corresponding scalers, making a balanced trade-off between recommendation accuracy and space overhead.

To verify the magnification of feature uniqueness in layer-wise quantization, we modify BiGeaR and propose two variants, denoted as BiGeaR${}_{w/o\,LW}$ and BiGeaR${}_{w/o\,FU}$. We report the results in Figure 4 by denoting Recall@20 and NDCG@20 in red and blue, respectively, and vary color brightness for different variants. From these results, we have the following explanations.

• •

  Firstly, BiGeaR${}_{w/o\,LW}$ discards the layer-wise quantization and adopts the conventional manner by quantizing the last outputs from $L$ convolution iterations. We fix dimension $d=256$ and vary layer number $L$ for BiGeaR, and only vary dimension $d$ for variant BiGeaR${}_{w/o\,LW}$ with fixed $L=2$. (1) Even by continuously increasing the dimension size from 64 to 1024, BiGeaR${}_{w/o\,LW}$ slowly improves both Recall@20 and NDCG@20 performance. (2) By contrast, our layer-wise quantization presents a more efficient capability in improving performance by increasing $L$ from 0 to 3. When $L=4$, BiGeaR usually exhibits a conspicuous performance decay, mainly because of the common over-smoothing issue in graph-based models (Li et al., 2019; Li et al., 2018). Thus, with a moderate size $d=256$ and convolution number $L\leq 3$, BiGeaR can attain better performance with acceptable computational complexity.

• •

  Secondly, BiGeaR${}_{w/o\,FU}$ omits the feature magnification effect by adopting the way used in HashGNN (Hamilton et al., 2017; Tan et al., 2020) as:

  (19)

  $$\begin{matrix}\boldsymbol{v}^{(l)}_{x}=\sum_{z\in\mathcal{N}(x)}\frac{1}{|\mathcal{N}(z)|}\boldsymbol{v}^{(l-1)}_{z}.\end{matrix}$$

  Similar to the analysis in § 3.1, such modification will finally disable the “magnification term” in Equation (18) and simplify it to the vanilla random walk for graph exploration. Although BiGeaR${}_{w/o\,FU}$ presents similar curve trends with BiGeaR when $L$ increases, the general performance throughout all five datasets is unsatisfactory compared to BiGeaR. This validates the effectiveness of BiGeaR’s effort in magnifying unique latent features, which enriches user-item representations and boosts Top-K recommendation performance accordingly.

We compare our gradient estimation with several recently studied estimators, such as Tanh-like (Qin et al., 2020; Gong et al., 2019), SSwish (Darabi et al., 2018), Sigmoid (Yang et al., 2019), and projected-based estimator (Liu et al., 2019) (denoted as PBE), by implementing them in BiGeaR. We report their Recall@20 in Figure 5 and compute the performance gain of our approach over these estimators accordingly. We have two main observations:

1. (1)

   Our proposed approach shows the consistent superiority over all other gradient estimators. These estimators usually use visually similar functions, e.g., tanh($\cdot$), to approximate $\operatorname{sign}(\cdot)$. However, these functions are not necessarily theoretically relevant to $\operatorname{sign}(\cdot)$. This may lead to inaccurate gradient estimation. On the contrary, as we explain in § 2.4, we transfer the unit-step function $u(\cdot)$ to $\operatorname{sign}(\cdot)$ by $\operatorname{sign}(\cdot)$ = 2$u(\cdot)$ - 1. Then we can further estimate the gradients of $\operatorname{sign}(\cdot)$ with the approximated derivatives of $u(\cdot)$. In other words, our approach follows the main optimization direction of factual gradients with $\operatorname{sign}(\cdot)$; and different from previous solutions, this guarantees the coordination in both forward and backward propagation.

2. (2)

   Furthermore, compared to the last four datasets, MovieLens dataset confronts a larger performance disparity between our approach and others. This is because MovieLens dataset is much denser than the other datasets, i.e., $\frac{\#Interactions}{\#Users\cdot\#Items}$ = 0.0419 $\gg$ {0.00084, 0.00267, 0.0013, 0.00062}, which means that users tend to have more item interactions and complicated preferences towards different items. Consequently, this posts a higher requirement for the gradient estimation capability in learning ranking information. Fortunately, the empirical results in Figure 5 demonstrate that our solution well fulfills these requirements, especially for dense interaction graphs.