{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"This notebook proposes a simple and fast forward approach based on Graph Embedding using the `Pytorch Geometric` library.","metadata":{}},{"cell_type":"markdown","source":"## Graph Embedding\nGraph embedding is the process of representing nodes in a graph in a low-dimensional vector space. This allows the structural information in the graph to be captured and analyzed using machine learning algorithms.\n\nGraph embedding methods aim to preserve the relationships between nodes in the graph as much as possible in the low-dimensional space. This allows for the discovery of patterns and relationships in the graph that may not be readily apparent from the raw data.\n\nThere are several different approaches to graph embedding, including matrix factorization, neural network-based methods, and random walk-based methods. Each approach has its own strengths and limitations, and which method is best depends on the specific problem at hand.\n\nIn this notebook we'll cover the biased Random Walk approach for link prediction","metadata":{}},{"cell_type":"markdown","source":"#### Preprocessing","metadata":{}},{"cell_type":"markdown","source":"For the preprocessing, I kept it very simple:\n\nAids represent nodes, whereas a edge represents two consecutives aids checked sequentially together within each session.\n\nThis figure shows how we model the interactions:\n\n![Representation of the Graph](https://user-images.githubusercontent.com/55285736/205647636-c32fc79b-e56f-4fe9-b126-d736642124f6.png)\n\n\nIt's important to note that we consider this as a homogenous undirected graph with one single entity ( aids ) and I didn't consider the temporal interactions between aids. \n\n\n**Special thanks to Radek Osmulki for the validation steps of the recommendation as well as the dataset he provided !**\n","metadata":{}},{"cell_type":"markdown","source":"For further reading:\n\n- Node2Vec Paper : https://cs.stanford.edu/people/jure/pubs/node2vec-kdd16.pdf.\n\n-  Radek local validation : https://www.kaggle.com/competitions/otto-recommender-system/discussion/364991\n\n- Radek Datasets for local validation : https://www.kaggle.com/datasets/radek1/otto-train-and-test-data-for-local-validation.\n\n- Stanford Video of Leskovec. PhD explaining Node2Vec : https://www.youtube.com/watch?v=Xv0wRy66Big","metadata":{}},{"cell_type":"markdown","source":"**If you like this notebook, please upvote! That will be of great help to me and will allow me to share more materials like this with you. Thank you! 😊**","metadata":{}},{"cell_type":"markdown","source":"## Libraries installation\n","metadata":{}},{"cell_type":"markdown","source":"We will need a couple of libraries that do not come preinstalled on the Kaggle VM. Let's install them here.","metadata":{}},{"cell_type":"code","source":"!pip install polars\n## GPU Version\n#!pip install pyg-lib -f https://data.pyg.org/whl/torch-1.12.0+cu116.html   \n!pip install torch==1.12.0+cu116 -f https://download.pytorch.org/whl/cu116/torch_stable.html\n!pip install torch-scatter torch-sparse torch-cluster torch-spline-conv torch-geometric -f https://data.pyg.org/whl/torch-1.12.0+cu116.html","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from tqdm import tqdm\nfrom collections import defaultdict\nimport numpy as np\nimport pandas as pd\nimport torch\nimport torch_geometric\nfrom torch_geometric.data import Data\nfrom torch_geometric.nn import Node2Vec\ntorch_geometric.__version__\nimport gc\nimport polars as pl","metadata":{"_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","papermill":{"duration":3.413687,"end_time":"2022-11-17T15:19:57.152549","exception":false,"start_time":"2022-11-17T15:19:53.738862","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2023-01-05T13:21:54.951410Z","iopub.execute_input":"2023-01-05T13:21:54.951834Z","iopub.status.idle":"2023-01-05T13:21:57.600398Z","shell.execute_reply.started":"2023-01-05T13:21:54.951753Z","shell.execute_reply":"2023-01-05T13:21:57.599345Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"device = 'cuda' if torch.cuda.is_available() else 'cpu'\nprint(device)","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:21:59.953910Z","iopub.execute_input":"2023-01-05T13:21:59.954966Z","iopub.status.idle":"2023-01-05T13:21:59.960322Z","shell.execute_reply.started":"2023-01-05T13:21:59.954905Z","shell.execute_reply":"2023-01-05T13:21:59.959281Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Build Graph","metadata":{"papermill":{"duration":0.179794,"end_time":"2022-11-17T15:19:57.512732","exception":false,"start_time":"2022-11-17T15:19:57.332938","status":"completed"},"tags":[]}},{"cell_type":"markdown","source":"Here I concatenate the rows of train of test and simply lagged the `aid` column by `session` to extract the `precedent_aid` of each row within each `session`\n\nEven with `polar`, I didn't have enough memory to compute this, please feel free to come up with a solution if you have !","metadata":{}},{"cell_type":"code","source":"# LOAD THREE CO-VISITATION MATRICES\ndef pqt_to_dict(df):\n    return df.groupby('aid_x').aid_y.apply(list).to_dict()\n\n\nDISK_PIECES = 4\ncandidates_number = 50\n\n\ntop_20_clicks = pqt_to_dict( pd.read_parquet(f'/kaggle/input/clicks-orders-carts-candidates/top_{candidates_number}_clicks_v6_0.pqt') )\nfor k in range(1, DISK_PIECES): \n    top_20_clicks.update( pqt_to_dict( pd.read_parquet(f'/kaggle/input/clicks-orders-carts-candidates/top_{candidates_number}_clicks_v6_{k}.pqt') ) )","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:22:03.738791Z","iopub.execute_input":"2023-01-05T13:22:03.739473Z","iopub.status.idle":"2023-01-05T13:23:04.866477Z","shell.execute_reply.started":"2023-01-05T13:22:03.739436Z","shell.execute_reply":"2023-01-05T13:23:04.865364Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"key_list=list(top_20_clicks.keys())\nval_list=list(top_20_clicks.values())","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:23:04.868579Z","iopub.execute_input":"2023-01-05T13:23:04.869077Z","iopub.status.idle":"2023-01-05T13:23:04.964450Z","shell.execute_reply.started":"2023-01-05T13:23:04.869041Z","shell.execute_reply":"2023-01-05T13:23:04.963414Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"edges = pl.DataFrame()\n\nedges  = edges.with_column(pl.Series(key_list).alias(\"aid\").cast(pl.Int32))","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:23:04.965794Z","iopub.execute_input":"2023-01-05T13:23:04.966959Z","iopub.status.idle":"2023-01-05T13:23:05.133619Z","shell.execute_reply.started":"2023-01-05T13:23:04.966895Z","shell.execute_reply":"2023-01-05T13:23:05.132385Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"edges  = edges.with_column(pl.Series(val_list).alias(\"neighbors\"))","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:23:05.136293Z","iopub.execute_input":"2023-01-05T13:23:05.136692Z","iopub.status.idle":"2023-01-05T13:23:09.319729Z","shell.execute_reply.started":"2023-01-05T13:23:05.136610Z","shell.execute_reply":"2023-01-05T13:23:09.318427Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"edges_ = edges.explode(\"neighbors\")","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:24:59.051499Z","iopub.execute_input":"2023-01-05T13:24:59.051881Z","iopub.status.idle":"2023-01-05T13:24:59.554359Z","shell.execute_reply.started":"2023-01-05T13:24:59.051849Z","shell.execute_reply":"2023-01-05T13:24:59.553310Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"edges_ = edges_.with_column(pl.col(\"neighbors\").cast(pl.Int32))","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:26:05.398681Z","iopub.execute_input":"2023-01-05T13:26:05.399473Z","iopub.status.idle":"2023-01-05T13:26:06.009912Z","shell.execute_reply.started":"2023-01-05T13:26:05.399425Z","shell.execute_reply":"2023-01-05T13:26:06.008691Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"edges_torch_T = torch.tensor(np.transpose(edges_[['aid','neighbors']].to_numpy()),dtype=torch.long)","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:26:21.991064Z","iopub.execute_input":"2023-01-05T13:26:21.992148Z","iopub.status.idle":"2023-01-05T13:26:23.452048Z","shell.execute_reply.started":"2023-01-05T13:26:21.992104Z","shell.execute_reply":"2023-01-05T13:26:23.451001Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"data = Data(edge_index=edges_torch_T)\nprint(data)","metadata":{"papermill":{"duration":0.406677,"end_time":"2022-11-17T15:20:04.943915","exception":false,"start_time":"2022-11-17T15:20:04.537238","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2023-01-05T13:26:37.970468Z","iopub.execute_input":"2023-01-05T13:26:37.970822Z","iopub.status.idle":"2023-01-05T13:26:37.978417Z","shell.execute_reply.started":"2023-01-05T13:26:37.970790Z","shell.execute_reply":"2023-01-05T13:26:37.977011Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"As you can see, our `data` variables represents the graph of interactions with the number of nodes that represents the number of unique aids ( 1855603 ), as well as the number of edges ( more than 200 millions ! ) that represent two consecutives aids checked together within a session.","metadata":{}},{"cell_type":"code","source":"del edges_torch_T,edges,edges_,key_list,val_list,top_20_clicks\ngc.collect()","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:27:10.869930Z","iopub.execute_input":"2023-01-05T13:27:10.870526Z","iopub.status.idle":"2023-01-05T13:27:14.250597Z","shell.execute_reply.started":"2023-01-05T13:27:10.870492Z","shell.execute_reply":"2023-01-05T13:27:14.249390Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Embedding graph using Node2Vec","metadata":{"papermill":{"duration":0.178202,"end_time":"2022-11-17T15:20:05.343671","exception":false,"start_time":"2022-11-17T15:20:05.165469","status":"completed"},"tags":[]}},{"cell_type":"markdown","source":"`Node2Vec`, simply said is an algorithm used to learn the representations of nodes in a graph.\n\nThe algorithm is based on the idea that a node's neighbors in a graph can provide valuable information about the node itself. \n\nCompared to the DeepWalk[1] Algorithm that does multiple unbiased random walks across all the node of the graph, Node2vec uses a biased random walk technique to explore the graph and learn the representations of the nodes, by using the parameters : `q` and `p`. This allows the algorithm to capture the structural properties of the graph, such as the node's role and its community, as well as its relationships with other nodes in the graph.\n\nThe intuition of Node2vec parameters `p` and `q` is that they mimic the behavior of two algorithms BFS (Breadth  First Strategy ) and DFS ( Depth First Strategy )  to explore the graph in differents ways and get differents resolutions of the network, in summary `p`  represents the Likelihood of immediately revisiting a node in the walk, whereas `q` is the ratio between BFS and DFS strategies.\n\nLet's see this exemple : if we want to have a high probability of transition to navigate/return back to the node, we set a low palue of `p`, whereas if we want to navigate farther away from the node we set a low value of `q`.\n\n\n![BFS vs DFS](https://user-images.githubusercontent.com/55285736/205650721-828f5d03-62cd-4580-b00e-9a83d97f1955.png)\n\n- DFS allows to explore the graph globally.\n\n- BFS allows to explore the graph locally,\n\nIn summary, Node2vec uses a Random Walk that can trade off between local and global views of the networks, the overall is optimized using SGD optimizer.\n\nOne of the key advantages of node2vec is that it can be used on large-scale graphs. It scales linearly with the number of nodes and edges in the graph, making it suitable for working with large-scale networks such as social networks and web graphs.\n\nThe node2vec algorithm has been applied to various tasks, such as node classification, community detection, and link prediction. In node classification, the learned node representations can be used as features in a machine learning model to predict the class of a node. In community detection, the node representations can be clustered to identify the communities in the graph. In link prediction, the node representations can be used to predict missing or future links in the graph.\n\nOverall, node2vec is a valuable tool for learning the representations of nodes in a graph. It can be applied to a wide range of tasks and is suitable for working with large-scale graphs, its steps can be summarized as below:\n1. Compute random walk probabilities.\n2. Simulate r random walks of length l starting from each node.\n3. Optimize the node2vec objective using SGD.\n \n\n\nThe algorithm has linear complexity, and all 3 steps are parallelizable.\n\n\n**( If you want me to give more details about the method, let me know with a comment :D )**\n","metadata":{}},{"cell_type":"code","source":"model = Node2Vec(data.edge_index, embedding_dim=32, \n                 walk_length=50,                        # lenght of rw\n                 context_size=5, walks_per_node=10,\n                 num_negative_samples=2, \n                 p=0.2, q=0.5,                             # bias parameters\n                 sparse=True).to(device)\n","metadata":{"papermill":{"duration":3.645433,"end_time":"2022-11-17T15:20:09.547361","exception":false,"start_time":"2022-11-17T15:20:05.901928","status":"completed"},"tags":[],"execution":{"iopub.status.busy":"2023-01-05T13:27:33.012077Z","iopub.execute_input":"2023-01-05T13:27:33.013302Z","iopub.status.idle":"2023-01-05T13:27:44.828356Z","shell.execute_reply.started":"2023-01-05T13:27:33.013254Z","shell.execute_reply":"2023-01-05T13:27:44.827310Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"loader = model.loader(batch_size=256, shuffle=True,\n                      num_workers=2)\noptimizer = torch.optim.SparseAdam(list(model.parameters()), lr=0.01)","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:28:11.770531Z","iopub.execute_input":"2023-01-05T13:28:11.770893Z","iopub.status.idle":"2023-01-05T13:28:11.777214Z","shell.execute_reply.started":"2023-01-05T13:28:11.770863Z","shell.execute_reply":"2023-01-05T13:28:11.776024Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"del data\ngc.collect()","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:28:15.450376Z","iopub.execute_input":"2023-01-05T13:28:15.450756Z","iopub.status.idle":"2023-01-05T13:28:15.691982Z","shell.execute_reply.started":"2023-01-05T13:28:15.450721Z","shell.execute_reply":"2023-01-05T13:28:15.690857Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":" def train():\n        model.train()\n        total_loss = 0\n        for pos_rw, neg_rw in tqdm(loader):\n            optimizer.zero_grad()\n            loss = model.loss(pos_rw.to(device), neg_rw.to(device))\n            loss.backward()\n            optimizer.step()\n            total_loss += loss.item()\n        return total_loss / len(loader)\n\nfor epoch in range(0, 20):\n    loss = train()\n    print(f'Epoch: {epoch:02d}, Loss: {loss:.4f}')\n\n","metadata":{"execution":{"iopub.status.busy":"2023-01-05T13:28:21.171547Z","iopub.execute_input":"2023-01-05T13:28:21.171913Z","iopub.status.idle":"2023-01-05T13:32:11.788595Z","shell.execute_reply.started":"2023-01-05T13:28:21.171883Z","shell.execute_reply":"2023-01-05T13:32:11.786937Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The strategy then is to use KNN method on the node embeddings to search for the  K most similar nodes, for each node of the graph.","metadata":{}},{"cell_type":"markdown","source":"For fast search, we use the `annoy` library that allows approximative neighbors search.","metadata":{}},{"cell_type":"code","source":"%%time\nfrom annoy import AnnoyIndex\n\nindex = AnnoyIndex(32, 'angular')\n\nfor idx,idx_embedding in enumerate(model.state_dict()['embedding.weight'].cpu()):\n    index.add_item(idx, idx_embedding)\n    \nindex.build(10)","metadata":{"papermill":{"duration":0.28166,"end_time":"2022-11-17T15:43:50.159342","exception":false,"start_time":"2022-11-17T15:43:49.877682","status":"completed"},"tags":[],"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"embeddings_node2vec = model.cpu().state_dict()['embedding.weight'].numpy()\n\nnp.save(\"node2vec_embeddings\",embeddings_node2vec)","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"del model, loader, optimizer, embeddings_node2vec\ngc.collect()\ntorch.cuda.empty_cache()","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Validation / Inference","metadata":{}},{"cell_type":"code","source":"def evaluate(path,mode=\"validation\",n_neighbors=20):\n\n\n    test = pl.read_parquet(path)\n\n    session_types = ['clicks', 'carts', 'orders']\n    test_session_AIDs = test.to_pandas().reset_index(drop=True).groupby('session')['aid'].apply(list)\n    test_session_types = test.to_pandas().reset_index(drop=True).groupby('session')['type'].apply(list)\n\n    del test\n    gc.collect()\n    labels = []\n\n    type_weight_multipliers = {0: 1, 1: 6, 2: 3}\n\n    for AIDs, types in zip(test_session_AIDs, test_session_types):\n        if len(AIDs) >= 20:\n                # if we have enough aids (over equals 20) we don't need to look for candidates! we just use the old logic\n            weights=np.logspace(0.1,1,len(AIDs),base=2, endpoint=True)-1\n            aids_temp=defaultdict(lambda: 0)\n            for aid,w,t in zip(AIDs,weights,types): \n                aids_temp[aid]+= w * type_weight_multipliers[t]\n\n            sorted_aids=[k for k, v in sorted(aids_temp.items(), key=lambda item: -item[1])]\n            labels.append(sorted_aids[:20])\n        else:\n            # here we don't have 20 aids to output -- we will use word2vec embeddings to generate candidates!\n            AIDs = list(dict.fromkeys(AIDs[::-1]))\n\n            # let's grab the most recent aid\n            most_recent_aid = AIDs[0]\n\n            # and look for some neighbors!\n            nns = [i for i in index.get_nns_by_item(most_recent_aid, n_neighbors+1)[1:]]\n\n\n            labels.append((AIDs+nns)[:n_neighbors])\n\n    labels_as_strings = [' '.join([str(l) for l in lls]) for lls in labels]\n\n    predictions = pd.DataFrame(data={'session_type': test_session_AIDs.index, 'labels': labels_as_strings})\n\n    prediction_dfs = []\n\n    for st in session_types:\n        modified_predictions = predictions.copy()\n        modified_predictions.session_type = modified_predictions.session_type.astype('str') + f'_{st}'\n        prediction_dfs.append(modified_predictions)\n\n    sub = pd.concat(prediction_dfs).reset_index(drop=True)\n    \n    del prediction_dfs, predictions,labels_as_strings, labels, test_session_types,test_session_AIDs\n    gc.collect()\n    if mode==\"test\":\n        sub.to_csv(\"submission.csv\",index=False)\n        return sub\n    else:\n\n        sub['labels_2'] = sub['labels'].apply(lambda x : [int(s) for s in x.split(' ')])\n        submission = pd.DataFrame()\n        submission['session'] = sub.session_type.apply(lambda x: int(x.split('_')[0]))\n        submission['type'] = sub.session_type.apply(lambda x: x.split('_')[1])\n        submission['labels'] = sub.labels_2.apply(lambda x : [item for item in x[:] ]) #.apply(lambda x: [int(i) for i in x.split(',')[:20]])\n        test_labels = pd.read_parquet('/kaggle/input/otto-train-and-test-data-for-local-validation/test_labels.parquet')\n        test_labels = test_labels.merge(submission, how='left', on=['session', 'type'])\n        del sub,submission\n        gc.collect()\n        gc.collect()\n        test_labels['hits'] = test_labels.apply(lambda df: len(set(df.ground_truth).intersection(set(df.labels))), axis=1)\n        test_labels['gt_count'] = test_labels.ground_truth.str.len().clip(0,20)\n        recall_per_type = test_labels.groupby(['type'])['hits'].sum() / test_labels.groupby(['type'])['gt_count'].sum() \n        score = (recall_per_type * pd.Series({'clicks': 0.1, 'carts': 0.30, 'orders': 0.60})).sum()\n\n        return score,recall_per_type","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Validation","metadata":{}},{"cell_type":"code","source":"path = \"/kaggle/input/otto-train-and-test-data-for-local-validation/test.parquet\"\nvalidation_score,recall_per_type = evaluate(path,mode=\"validation\",n_neighbors=20)","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(validation_score)","metadata":{},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(recall_per_type)","metadata":{},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"### Inference / Submission","metadata":{}},{"cell_type":"code","source":"path = \"/kaggle/input/otto-full-optimized-memory-footprint/test.parquet\"\ntest_submission = evaluate(path,mode=\"test\",n_neighbors=20)","metadata":{"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"For further improvements:\n\n**- one can consider the problem as a bipartite graph ( heterogenous )**\n\n**- Consider the temporal interactions.**\n\n**- Add weights to the edges.**\n\n**- Re-think the edges attributions within a session ( for exemple two consecutive aids checked within a session are linked if and only if the timestamp scope between them is less than 1 day )**","metadata":{}}]}