FPSR+ Demonstration.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1cN-BpEGaSf5"
      },
      "source": [
        "# FPSR+\n",
        "------------\n",
        "This is an demonstration of our paper:\n",
        "\n",
        "<p align=\"center\" width=\"40%\">\n",
        "    <kbd><img width=\"40%\" src=\"https://raw.githubusercontent.com/Joinn99/RepositoryResource/master/Illustration_FPSRPlus.svg\"> </kbd>\n",
        "</p>\n",
        "\n",
        "> Tianjun Wei, Jianghong Ma, Tommy W.S. Chow. Fine-tuning Partition-aware Item Similarities for Efficient and Scalable Recommendation. In WWW 2023. [[arxiv](https://arxiv.org/abs/2207.05959)] [[Github](https://github.com/Joinn99/FPSR)]\n",
        "\n",
        "> Tianjun Wei, Tommy W.S. Chow, Jianghong Ma. FPSR+: Towards Robust, Efficient and Scalable Collaborative Filtering with Partition-aware Item Similarity Modeling. In TKDE 2024. [[Github](https://github.com/Joinn99/FPSR)]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8pxSpTa9ZoTy"
      },
      "source": [
        "## Preprocessing"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "FrbhQmJjGF3I",
        "cellView": "form"
      },
      "outputs": [],
      "source": [
        "#@title Environment Setting\n",
        "#@markdown FPSR is implemented based on the recommendation toolbox [RecBole](https://recbole.io/).\n",
        "%%capture\n",
        "! pip install recbole==1.2.0"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "cellView": "form",
        "id": "pqa6o51yExY_"
      },
      "outputs": [],
      "source": [
        "#@title Download Dataset\n",
        "#@markdown Here we use four public datasets:<br>\n",
        "#@markdown - [Amazon-cds](https://github.com/xue-pai/UltraGCN/blob/main/data/amazoncds/)\n",
        "#@markdown - [Douban](https://github.com/librahu/HIN-Datasets-for-Recommendation-and-Network-Embedding/blob/master/Douban%20Book/user_book.dat)\n",
        "#@markdown - [Gowalla](https://github.com/kuandeng/LightGCN/blob/master/Data/gowalla/)\n",
        "#@markdown - [Yelp2018](https://github.com/kuandeng/LightGCN/blob/master/Data/yelp2018)\n",
        "\n",
        "#@markdown We also provide processed datasets that conform to the RecBole data format, which can be downloaded [here](https://github.com/Joinn99/FPSR/tree/master/Data).\n",
        "\n",
        "%%capture\n",
        "! git clone https://github.com/Joinn99/FPSR\n",
        "! cd FPSR && unzip -o \"Data/*.zip\" -d /content"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "cellView": "form",
        "id": "7NnQ5JnKb-p1"
      },
      "outputs": [],
      "source": [
        "#@title Configuation\n",
        "#@markdown Here we list the configurations of the experiment.\n",
        "#@markdown For a detailed description of the configuration, please refer to [RecBole API](https://recbole.io/docs/user_guide/config_settings.html).\n",
        "\n",
        "CONFIG = {\n",
        "    \"seed\": 2026,\n",
        "    \"reproducibility\": True,\n",
        "\n",
        "    \"eval_args\":{\n",
        "        \"split\": {'RS': [0.7, 0.15, 0.15]},\n",
        "        \"order\": 'RO',\n",
        "        \"group_by\": 'user',\n",
        "        \"mode\": 'full'\n",
        "    },\n",
        "    \"topk\": [10, 20],\n",
        "    \"metrics\": ['Recall', 'NDCG'],\n",
        "    \"metric_decimal_place\": 6,\n",
        "\n",
        "    \"data_path\": 'Data',\n",
        "    \"load_col\": {\n",
        "        \"inter\": ['user_id', 'item_id'],\n",
        "        \"user\": ['user_id'],\n",
        "        \"item\": ['item_id']\n",
        "    },\n",
        "    \"USER_ID_FIELD\": 'user_id',\n",
        "    \"ITEM_ID_FIELD\": 'item_id',\n",
        "\n",
        "    \"train_neg_sample_args\":{\n",
        "        \"sample_num\": 1\n",
        "    },\n",
        "    \"train_batch_size\": 524288,\n",
        "    \"eval_batch_size\": 1048576,\n",
        "    \"filter_inter_by_user_or_item\": False,\n",
        "    \"epochs\": 1,\n",
        "    \"eval_step\": 0,\n",
        "}\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "f5ytkUIsbn_B"
      },
      "source": [
        "### Hyperparameters\n",
        "Here we list the hyperparameter setting of FPSR. To evaluate the performance of FPSR with different hyperparameters, modify the values in `FPSR_HYPER` and select `Runtime->Run after`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "k5R7vKwlMPfO"
      },
      "outputs": [],
      "source": [
        "DATASET = {\n",
        "    'dataset': 'douban'\n",
        "}\n",
        "\n",
        "FPSR_HYPER = {\n",
        "    \"eigenvectors\": 256,\n",
        "    \"opti_iter\": 50,\n",
        "    \"lambda\": 0.2,\n",
        "    \"rho\": 500,\n",
        "    \"theta_1\": 0.8,\n",
        "    \"theta_2\": 0.1,\n",
        "    \"eta\": 1.0,\n",
        "    \"tol\": 5e-3,\n",
        "    \"tau\": 0.5,\n",
        "    \"pop_ratio\": 0.1\n",
        "}\n",
        "\n",
        "CONFIG.update(DATASET)\n",
        "CONFIG.update(FPSR_HYPER)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7hNBSzOCZszh"
      },
      "source": [
        "## Model Implementation"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "id": "jHuhZcigM0lJ",
        "cellView": "form"
      },
      "outputs": [],
      "source": [
        "#@title FPSR+\n",
        "#@markdown This cell includes a complete implementation of FPSR model.\n",
        "#@markdown You can find it at [Github](https://github.com/Joinn99/FPSR/blob/torch/FPSR/model.py).\n",
        "\n",
        "r\"\"\"\n",
        "FPSR\n",
        "################################################\n",
        "Reference:\n",
        "    Tianjun Wei et al. \"Fine-tuning Partition-aware Item Similarities for Efficient and Scalable Recommendation.\" in WWW 2023.\n",
        "    Tianjun Wei et al. \"FPSR+: Towards Robust, Efficient and Scalable Collaborative Filtering with Partition-aware Item Similarity Modeling.\" in IEEE TKDE.\n",
        "Reference code:\n",
        "    https://github.com/Joinn99/FPSR/tree/torch\n",
        "\"\"\"\n",
        "\n",
        "import torch\n",
        "import numpy as np\n",
        "import scipy.sparse as sp\n",
        "\n",
        "from recbole.utils import InputType\n",
        "from recbole.utils.enum_type import ModelType\n",
        "from recbole.model.abstract_recommender import GeneralRecommender\n",
        "\n",
        "\n",
        "class FPSR_Plus(GeneralRecommender):\n",
        "    input_type = InputType.POINTWISE\n",
        "    type = ModelType.TRADITIONAL\n",
        "\n",
        "    def __init__(self, config, dataset):\n",
        "        super().__init__(config, dataset)\n",
        "\n",
        "        # load parameters info\n",
        "        # int type: Num of eigenvectors extracted for W\n",
        "        self.eigen_dim = config['eigenvectors']\n",
        "        self.lambda_ = config['lambda']         # float32 type: Lambda\n",
        "        self.rho = config['rho']                # float32 type: Rho\n",
        "        self.theta_1 = config['theta_1']        # float32 type: Theta_1\n",
        "        self.theta_2 = config['theta_2']        # float32 type: Theta_2\n",
        "        self.eta = config['eta']                # float32 type: Eta\n",
        "        # float32 type: Threshold to filter out small values\n",
        "        self.tol = config['tol']\n",
        "        # float32 type: Size ratio of partitions\n",
        "        self.tau = config['tau']\n",
        "        self.pop_ratio = config['pop_ratio']\n",
        "\n",
        "        self.p_list = []\n",
        "\n",
        "        # dummy params for recbole\n",
        "        # Dummy pytorch parameters required by Recbole\n",
        "        self.dummy_param = torch.nn.Parameter(torch.zeros(1))\n",
        "\n",
        "        # load dataset info\n",
        "        self.inter = dataset.inter_matrix(\n",
        "            form='coo')   # User-item interaction matrix\n",
        "        self.inter = torch.sparse_coo_tensor(\n",
        "            torch.LongTensor(np.array([self.inter.row, self.inter.col])),\n",
        "            torch.FloatTensor(self.inter.data),\n",
        "            size=self.inter.shape, dtype=torch.float\n",
        "        ).coalesce().to(self.device)\n",
        "\n",
        "        # storage variables for item similarity matrix S\n",
        "        self.S_indices = []\n",
        "        self.S_values = []\n",
        "\n",
        "        # training process\n",
        "        self.item_list = []\n",
        "        self.update_W()\n",
        "\n",
        "        # calaulate W and generate first split\n",
        "        pop_split = self.partitioning(self.V, pop=True)\n",
        "        self.pop_list = torch.arange(self.n_items, device=self.device)[torch.where(pop_split)[0]]\n",
        "\n",
        "        first_split = self.partitioning(self.V)\n",
        "        self.update_S(torch.arange(self.n_items, device=self.device)[\n",
        "                      torch.where(first_split)[0]])   # recursive paritioning #1\n",
        "        self.update_S(torch.arange(self.n_items, device=self.device)[\n",
        "                      torch.where(~first_split)[0]])  # recursive paritioning #2\n",
        "\n",
        "        for ilist in self.item_list:\n",
        "            self.item_similarity(ilist)\n",
        "\n",
        "        self.S = torch.sparse_coo_tensor(indices=torch.cat(self.S_indices, dim=1),\n",
        "                                         values=torch.cat(\n",
        "                                             self.S_values, dim=0),\n",
        "                                         size=(self.n_items, self.n_items)).coalesce().T.to_sparse_csr()\n",
        "\n",
        "\n",
        "        del self.S_indices, self.S_values\n",
        "\n",
        "    def _degree(self, inter_mat=None, dim=0, exp=-0.5) -> torch.Tensor:\n",
        "        r\"\"\"Get the degree of users and items.\n",
        "\n",
        "        Returns:\n",
        "            Tensor of the node degrees.\n",
        "        \"\"\"\n",
        "        if inter_mat is None:\n",
        "            inter_mat = self.inter\n",
        "        d_inv = torch.nan_to_num(torch.sparse.sum(\n",
        "            inter_mat, dim=dim).to_dense().pow(exp), nan=0, posinf=0, neginf=0)\n",
        "        return d_inv\n",
        "\n",
        "    def _svd(self, mat, k) -> torch.Tensor:\n",
        "        r\"\"\"Perform Truncated singular value decomposition (SVD) on\n",
        "        the input matrix, return top-k eigenvectors.\n",
        "\n",
        "        Returns:\n",
        "            Tok-k eigenvectors.\n",
        "        \"\"\"\n",
        "        _, _, V = torch.svd_lowrank(mat, q=max(4*k, 32), niter=10)\n",
        "        return V[:, :k]\n",
        "\n",
        "    def _norm_adj(self, item_list=None) -> torch.Tensor:\n",
        "        r\"\"\"Get the normalized item-item adjacency matrix for a group of items.\n",
        "\n",
        "        Returns:\n",
        "            Sparse tensor of the normalized item-item adjacency matrix.\n",
        "        \"\"\"\n",
        "        if item_list is None:\n",
        "            vals = self.inter.values() * \\\n",
        "                self.d_i[self.inter.indices()[1]].squeeze()\n",
        "            return torch.sparse_coo_tensor(\n",
        "                self.inter.indices(),\n",
        "                self._degree(dim=1)[self.inter.indices()[0]] * vals,\n",
        "                size=self.inter.shape, dtype=torch.float\n",
        "            ).coalesce()\n",
        "        else:\n",
        "            inter = self.inter.index_select(dim=1, index=item_list).coalesce()\n",
        "            vals = inter.values() * \\\n",
        "                self.d_i[item_list][inter.indices()[1]].squeeze()\n",
        "            return torch.sparse_coo_tensor(\n",
        "                inter.indices(),\n",
        "                self._degree(inter, dim=1)[inter.indices()[0]] * vals,\n",
        "                size=inter.shape, dtype=torch.float\n",
        "            ).coalesce()\n",
        "\n",
        "    def update_W(self) -> None:\n",
        "        r\"\"\"Derive the global-level information metrix W, and use the eigenvector\n",
        "        with the second largest eigenvalue to perform first graph partitioning.\n",
        "\n",
        "        \"\"\"\n",
        "        self.d_i = self._degree(dim=0).reshape(-1, 1)\n",
        "        self.d_i_inv = self._degree(dim=0, exp=0.5).reshape(1, -1)\n",
        "        self.V = self._svd(self._norm_adj(), self.eigen_dim)\n",
        "\n",
        "    def partitioning(self, V, pop=False) -> torch.Tensor:\n",
        "        r\"\"\"Perform graph bipartitioning.\n",
        "\n",
        "        Returns:\n",
        "            Paritioning result.\n",
        "        \"\"\"\n",
        "        if pop:\n",
        "            pop_thres = torch.quantile(self.d_i_inv, 1 - self.pop_ratio)\n",
        "            split = self.d_i_inv.squeeze() >= pop_thres\n",
        "        else:\n",
        "            split = V[:, 1] >= 0\n",
        "            if split.sum() == split.shape[0] or split.sum() == 0:\n",
        "                split = V[:, 1] >= torch.median(V[:, 1])\n",
        "        return split\n",
        "\n",
        "    def update_S(self, item_list) -> None:\n",
        "        r\"\"\"Derive partition-aware item similarity matrix S in each partition.\n",
        "\n",
        "        \"\"\"\n",
        "        if item_list.shape[0] <= self.tau * self.n_items:\n",
        "            # If the partition size is samller than size limit, model item similarity for this partition.\n",
        "            self.item_list.append(item_list)\n",
        "        else:\n",
        "            # If the partition size is larger than size limit, perform graph partitioning on this partition.\n",
        "            split = self.partitioning(self._svd(self._norm_adj(item_list), 2))\n",
        "            self.update_S(item_list[torch.where(split)[0]])\n",
        "            self.update_S(item_list[torch.where(~split)[0]])\n",
        "\n",
        "    def item_similarity(self, item_list) -> torch.Tensor:\n",
        "        r\"\"\"Update partition-aware item similarity matrix S in a specific partition.\n",
        "\n",
        "        Returns:\n",
        "            Partition-aware item similarity matrix of a partition.\n",
        "        \"\"\"\n",
        "        # Initialize\n",
        "        print(\"Part {:d}: \".format(item_list.shape[0]), end=\"\")\n",
        "        combined = torch.cat([item_list, self.pop_list, self.pop_list], dim=0)\n",
        "        uniques, counts = combined.unique(return_counts=True)\n",
        "        difference = uniques[counts == 2]\n",
        "        aug_list = torch.cat([item_list, difference], dim=0)\n",
        "        deaug_list = item_list\n",
        "\n",
        "        full_mat = self.inter.index_select(dim=1, index=aug_list).to_dense()\n",
        "\n",
        "        W = self.lambda_ * self.d_i[aug_list, :] * self.V[aug_list, :] @ \\\n",
        "            self.V[deaug_list, :].T * self.d_i_inv[:, deaug_list]\n",
        "\n",
        "        Q_hat = torch.mm(full_mat.T, full_mat) + self.theta_2 * \\\n",
        "            torch.diag(\n",
        "                torch.pow(self.d_i_inv[:, aug_list].squeeze(), 2)) + self.eta\n",
        "        del full_mat\n",
        "\n",
        "        Z_aux = Q_hat[:, :deaug_list.shape[0]] - Q_hat @ W\n",
        "        del W\n",
        "\n",
        "        Q_inv = torch.inverse(\n",
        "            Q_hat + self.rho * torch.eye(Q_hat.shape[0], device=self.device))\n",
        "        diag_inv = torch.diag(Q_inv)[:deaug_list.shape[0]] + 1e-10\n",
        "        del Q_hat\n",
        "\n",
        "        Z_aux = Q_inv @ Z_aux\n",
        "\n",
        "        Phi = torch.zeros_like(Z_aux, device=self.device)\n",
        "        S = torch.zeros_like(Z_aux, device=self.device)\n",
        "        for _ in range(50):\n",
        "            # Iteration\n",
        "            Z_tilde = Z_aux + Q_inv @ (self.rho * (S - Phi))\n",
        "            gamma = torch.diag(Z_tilde) / diag_inv\n",
        "            Z = Z_tilde - Q_inv[:, :deaug_list.shape[0]] * gamma                                 # Update Z\n",
        "            S = torch.clip(Z + Phi - self.theta_1 /\n",
        "                           self.rho, min=0)    # Update S\n",
        "            Phi += Z - S                                                # Update Phi\n",
        "        S = torch.where(S >= self.tol, S, 0).to_sparse_coo()\n",
        "        self.S_indices.append(aug_list[S.indices()])\n",
        "        self.S_values.append(S.values())\n",
        "\n",
        "    def forward(self):\n",
        "        pass\n",
        "\n",
        "    def calculate_loss(self, interaction):\n",
        "        return torch.nn.Parameter(torch.zeros(1))\n",
        "\n",
        "    def predict(self, interaction):\n",
        "        user = self.inter.index_select(\n",
        "            dim=0, index=interaction[self.USER_ID]).to_dense()\n",
        "        item = self.S.index_select(\n",
        "            dim=1, index=interaction[self.ITEM_ID]).to_dense()\n",
        "        d_i_inv = self.d_i_inv[:, interaction[self.ITEM_ID]]\n",
        "        V = self.V[interaction[self.ITEM_ID], :]\n",
        "\n",
        "        r = torch.mul(item.T, user).sum(dim=-1)\n",
        "        r += self.lambda_ * \\\n",
        "            torch.mul(user * self.d_i.T @ self.V, V * d_i_inv.T).sum(dim=-1)\n",
        "        return r\n",
        "\n",
        "    def full_sort_predict(self, interaction) -> torch.Tensor:\n",
        "        user = self.inter.index_select(\n",
        "            dim=0, index=interaction[self.USER_ID]).to_dense()\n",
        "        r = torch.sparse.mm(self.S, user.T).T\n",
        "        r += self.lambda_ * user * self.d_i.T @ self.V @ self.V.T * self.d_i_inv\n",
        "        return r"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9spbyRBwb0dn"
      },
      "source": [
        "## Running"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "htpZ3NxHYlKP",
        "outputId": "cafde3db-8bd2-4677-ec32-a6d868050e06"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stderr",
          "text": [
            "WARNING:root:command line args [-f /root/.local/share/jupyter/runtime/kernel-820c5192-fe2d-4ec5-8bad-4c11e90b7220.json] will not be used in RecBole\n"
          ]
        },
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "==========Preprocessing==========\n",
            "Configuration loading complete.\n",
            "Data loading complete.\n",
            "============Training=============\n",
            "(This step may last several minutes)\n",
            "Part 8709: Part 9414: Part 4225: Training complete.\n",
            "===========Evaluation============\n",
            "Evaluation results:\n",
            "RECALL@10 : 0.166019\n",
            "RECALL@20 : 0.218151\n",
            "NDCG@10   : 0.200177\n",
            "NDCG@20   : 0.201788\n"
          ]
        }
      ],
      "source": [
        "r\"\"\"\n",
        "Code reference: https://recbole.io/docs/developer_guide/customize_models.html\n",
        "\"\"\"\n",
        "\n",
        "import warnings\n",
        "from recbole.utils import init_seed\n",
        "from recbole.trainer import Trainer\n",
        "from recbole.config import Config\n",
        "from recbole.data import create_dataset, data_preparation\n",
        "\n",
        "warnings.filterwarnings('ignore')\n",
        "\n",
        "print('='* 10 + 'Preprocessing' + '=' * 10)\n",
        "config = Config(model=FPSR_Plus, config_dict=CONFIG)\n",
        "init_seed(config['seed'], config['reproducibility'])\n",
        "print(\"Configuration loading complete.\")\n",
        "\n",
        "# dataset filtering\n",
        "dataset = create_dataset(config)\n",
        "train_data, valid_data, test_data = data_preparation(config, dataset)\n",
        "print(\"Data loading complete.\")\n",
        "\n",
        "print('='* 12 + 'Training' + '=' * 13)\n",
        "print(\"(This step may last several minutes)\")\n",
        "# model loading and initialization\n",
        "model = FPSR_Plus(config, train_data.dataset).to(config['device'])\n",
        "\n",
        "# trainer loading and initialization\n",
        "trainer = Trainer(config, model)\n",
        "\n",
        "# model training\n",
        "_, _ = trainer.fit(train_data, valid_data)\n",
        "\n",
        "print(\"Training complete.\")\n",
        "\n",
        "print('='* 11 + 'Evaluation' + '=' * 12)\n",
        "# model evaluation\n",
        "test_result = trainer.evaluate(test_data)\n",
        "print(\"Evaluation results:\")\n",
        "for metric, value in test_result.items():\n",
        "  print('{:10s}: {:.6f}'.format(metric.upper(), value))"
      ]
    }
  ],
  "metadata": {
    "accelerator": "GPU",
    "colab": {
      "provenance": []
    },
    "gpuClass": "standard",
    "kernelspec": {
      "display_name": "SparseRec",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.11.0"
    },
    "vscode": {
      "interpreter": {
        "hash": "933075f399f88ee3a7bc96289e7bedd6322a6307b0e261e2bc2c90799eef1243"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}