Paper Notes: IntentGC

IntentGC: a Scalable Graph Convolution Framework Fusing Heterogeneous Information for Recommendation

• LINK: https://arxiv.org/abs/1907.12377

• CLASSIFICATION: RECOMMENDER-SYSTEM, HETEROGENEOUS NETWORK, GCN

• YEAR: Submitted on 24 Jul 2019

• FROM: KDD 2019

• WHAT PROBLEM TO SOLVE: The sparsity of user-item interactions (i.e., explicit preferences) on websites remains a big challenge for predicting users’ behaviors. Although research efforts have been made in utilizing some auxiliary information (e.g., social relations between users) to solve the problem, the existing rich heterogeneous auxiliary relationships are still not fully exploited. Moreover, previous works relied on linearly combined regularizers and suffered parameter tuning.

  We find that all previous works only captured one type of auxiliary information for users and/or one type for items in the model, while ignoring a plenty of additional heterogeneous relationships on the graph.

  

• SOLUTION: In this work, we collect abundant relationships from common user behaviors and item information, and propose a novel framework named IntentGC to leverage both explicit preferences and heterogeneous relationships by graph convolutional networks. In addition to the capability of modeling heterogeneity, IntentGC can learn the importance of different relationships automatically by the neural model in a nonlinear sense. To apply IntentGC to web-scale applications, we design a faster graph convolutional model named IntentNet by avoiding unnecessary feature interactions.

• CORE POINT:

  • Difference between IntentGC and many state-of-the-art GCN models

    1. Their model considers only item information, while ignoring users and auxiliary objects.
    2. To scale up, GraphSage needs to sample many clustered mini-graphs of items for embedding reuse. However, it is hard to find such clustered mini-graphs that contain both users and items, due to the sparsity issue mentioned above.
    3. Their method is proposed for homogeneous networks, while user-item graphs studied in this work are heterogeneous.

  • Innovative points of IntentGC

    1. Fully exploiting auxiliary information

       To facilitate modeling and improve robustness, we translate auxiliary relationships of first order proximity into more robust weighted relationships of second order proximity.

       With different types of auxiliary objects, we can generate heterogeneous relationships of second-order proximity. IntentGC automatically determines the weights of different types of relationships in training.

       

    2. Faster graph convolution

       The key idea of IntentNet is to avoid unnecessary feature interactions by dividing the functionality of graph convolution into two components: a vector-wise convolution component for neighborhood feature propagation and a fully-connected network component for node feature interaction.

    3. Dual graph convolution in heterogeneous networks

       First, we take advantage of two independent IntentNets that separately operate on user nodes and item nodes. After nonlinear projection through the fully-connected network in the respective IntentNet, the obtained embeddings of users and items can be deemed to form a common space. Then, with training guided by explicit preferences, relevance can be assessed between users and items in the space.

  • Usage of auxiliary information

    Unlike previous works of capturing auxiliary relationships in the objective function with a regularizer, which is linear and heavily depends on handcraft parameter tuning, our method can automatically learn the importance of different auxiliary relationships through non-linear neural network.

    We note that auxiliary information could also be designed as node input features. However, nodes sharing some input features would not be near in the high-level embedding space due to the complex neural network projection.

  • User-Item recommendation

    We can formulate the user-item recommendation problem as a link prediction problem on graph in the following:

    Input: A HIN $G = (V, E)$G=(V,E) based on historical data.

    Output: A predicted edge set $\hat{E}^p_{label}$E^labelp​ , which is the prediction of the real edge set $E^p_{label}$Elabelp​ on $G^p$Gp .

  • Methodology

    • Network Translation

      In this paper, we utilize the second-order proximity to capture the similarity between two users (or items), which is measured by the number of common auxiliary neighbors of the same type shared by them.

    • Faster Convolutional Network: IntentNet

      

      • Vector-wise convolution operation

        During representation learning, there are mainly two tasks in the convolution operation: One is to learn the interactions between self node and its neighborhood, which determines how neighborhood boosts the results; the other one is to learn the interactions between different dimensions of the embedding space, which will extract useful combinatory features automatically.

        A key insight is that the interaction between feature $h_i$hi​ in h$^{k−1}_u$uk−1​ and $h_j (j ≠ i)$hj​(j​=i) in h$^{k −1}_{N(u)}$N(u)k−1​ is less informative.

        Based on this observation, we designed a vector-wise convolution function in the following:

        

        Each local filter can be viewed as learning how self node and neighborhood interact in a vector-wise manner, the multiple local filters here ensure a rich information extraction capability.

      • IntentNet

        With the core idea of dividing the work of graph convolution into two components: vector-wise convolution for learning the neighborhood’s utility, and fully-connected layers for extracting the node-level combinatory features.

        In practice, IntentGC is not only more efficient than conventional GCNs but also more effective in performance. A probable reason is that IntentGC can avoid useless feature interactions and is more robust to overfitting.

      • Complexity

        m to denote the sizes of representation vectors in different layers, ρ-neighborhood, L is the number of local filters.

        The complexity of the convolution operation:

        1. IntentNet: $O(m∗(ρ+L))≈O(m)$O(m∗(ρ+L))≈O(m)
        2. GraphSAGE: $O(m∗(ρ+m)) ≈ O(m2)$O(m∗(ρ+m))≈O(m2)

        q-stacked graph convolution:

        1. IntentNet: $O(ρ^{q−1}∗m+m^2)$O(ρq−1∗m+m2)
        2. GraphSAGE: $O(ρ^{q−1} ∗ m^2)$O(ρq−1∗m2)

      • Heterogeneous relationships

        

    • Dual Graph Convolution in HIN

      We employ two IntentNets, IntentNet$u$u and IntentNet$v$v , for users and items respectively. By iteratively running q times of convolutional forward propagation as in Eq (1), Eq (5) and Eq (4) and additional dense forward propagation via the fully-connected layers, we can obtain the final user and item representations z$u$u , z$v$v , by IntentNet$u$u and IntentNet$v$v respectively.

      Triplet loss function:

      

    • The IntentGC Framework

      

  • Experiments

    • Datasets

      

    • Compared methods

      DeepWalk, GraphSage, DSPR, Metapath2vec++, BiNE, IntentGC(Single), IntentGC(All)

    • Hyper-parameter settings

      

    • System architecture

      

• EXISTING PROBLEMS: No Taobao dataset.

• IMPROVEMENT IDEAS: 404