# INDUCTIVE MATRIX COMPLETION BASED ON GRAPH NEURAL NETWORKS

### INDUCTIVE MATRIX COMPLETION BASED ON GRAPH NEURAL NETWORKS

To make matrix completion inductive, most previous works use content(side information) to make prediction.

Problems: High-quality content is noe always available and can be hard to extract

Conventional methods: low-rank rating matrix decomposition. In IMC: r_{ij}=x_i^T Q y_j, where Q is a learnable matrix modeling the feature interactionms. IMC methods have strong constraints on the content quality.

In 2018, Hartford propose exchangeable matrix layers which do not rely on side information while needing the whole rating matrix as the input, which tends to lead to a scalability challenges for practical datasets.

In this paper, a novel inductive matrix completion method that does not use any content. The key component is local graph pattern. Predicting the unknown ratings converts equivalentl to predicting labeled links in the corresponding bipartite graphs.

IGMC uses a graph-level GNN to learn representations for subgraphs.

##### IGMC
• Enclosing subgraph extraction

BFS procedure for extracting h-hop enclosing subgraphs:

• Node labeling

Assign an integer to every node in the subgraph. The purpose is to mark different roles for nodes.

• target user and target item

• User-type nodes and item-type nodes

0, 1 -> 2i, 2i+1

• IGMC purely relies on graph patterns within local enclosing subgraphs. -> inductive (compared to GC-MC 2018, which is a transductive method)
• Graph neural network architecture

Two key components:

• Message passing layers: extract a feature vector for each node in the subgraph.

R-GCN:

$$\mathbf{x}_{i}^{l+1}=\mathbf{W}_{0}^{l} \mathbf{x}_{i}^{l}+\sum_{r \in \mathcal{R}} \sum_{j \in \mathcal{N}_{r}(i)} \frac{1}{\left|\mathcal{N}_{r}(i)\right|} \mathbf{W}_{r}^{l} \mathbf{x}_{j}^{l}$$

$$\mathbf{h}_{i}=\operatorname{concat}\left(\mathbf{x}_{i}^{1}, \mathbf{x}_{i}^{2}, \ldots, \mathbf{x}_{i}^{L}\right)$$

• A pooling layer: summarize a subgraph representation from node features

\mathbf{g}=\operatorname{concat}\left(\mathbf{h}_{u}, \mathbf{h}_{v}\right), \quad
\hat{r}=\mathbf{w}^{\top} \sigma(\mathbf{W} \mathbf{g})

• Model training

Loss function:

$$\mathcal{L}=\frac{1}{|{(u, v) \mid \mathbf{\Omega}_{u, v}=1}|} \sum_{(u, v): \boldsymbol{\Omega}_{u, v}=1}\left(R_{u, v}-\hat{R}_{u, v}\right)^{2}$$

$$\mathcal{L}_{\mathrm{ARR}}=\sum_{i=1,2, \ldots,|\mathcal{R}|-1}\left\Vert\mathbf{W}_{r_{i+1}}-\mathbf{W}_{r_{i}}\right\Vert_{F}^{2}$$

$$\mathcal{L}_{\mathrm{final}} = \mathcal{L} + \lambda \mathcal{L}_{\mathrm{ARP}}$$

$\mathcal{L}_{\mathrm{ARR}}$ encourages rating adjacent to each other to have similar parameter matrices.

• Comparison to GC-MC

• IGMC uses a graph-level GNN to map the enclosing subgraph whereas it has a higher complexity.

• GC-MC uses a node-level GNN on the bipartite graph G to learn embeddings to predict the rating. The main drawback is that it fails to model interactions and correspondences between the nodes due to the independent consideration for nodes.