INDUCTIVE MATRIX COMPLETION BASED ON GRAPH NEURAL NETWORKS

通过admin

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.

6C0AD29B-A623-4420-8841-1B677155D193

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

IGMC
  • Enclosing subgraph extraction

    BFS procedure for extracting h-hop enclosing subgraphs:

6C0AD29B-A623-4420-8841-1B677155D193

  • 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

    21965B47-879B-4C5D-A897-8D397C513B39

    • 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.

    57FB8869-F213-4614-A1CC-098EE64A36BC

87451997-3D0A-4C02-BE6F-FEB3792D38F8

关于作者

admin administrator

发表评论