Due to the convenience of mobile devices, the online games have become an important part for user entertainments in reality, creating a demand for friend recommendation in online games.However, none of existing approaches can effectively incorporate the multi-modal user features (e.g., images and texts) with the structural information in the friendship graph, due to the following limitations: (1) some of them ignore the high-order structural proximity between users, (2) some fail to learn the pairwise relevance between users at modality-specific level, and (3) some cannot capture both the local and global user preferences on different modalities.By addressing these issues, in this paper, we propose an end-to-end model FROG that better models the user preferences on potential friends.Comprehensive experiments on both offline evaluation and online deployment at Tencent have demonstrated the superiority of FROG over existing approaches.The source code of this paper can be found at https://github.com/socialalgo/FROG.

Recently, huge interests in both academic and in-dustry have been posed to Graph Neural Network due to its power on revealing the topological information inside the data. To support the real-world applications, most of (if not all) which contain large-scale graphs with billions of edges, a number of graph-based deep learning systems have been proposed and implemented. However, all of them fail to efficiently process the dynamic graphs in terms of both memory and time cost. The state-of-the-art suffers from two issues: (1) expensive memory consumption due to the huge indexing overhead of numerous key-value pairs in traditional key-value topology storage and (2) inefficient dynamic updating due to the heavy updates on indexing structures for weighted neighbor sampling. In this paper, we proposed a Dynamic Graph-based Learning System PiatoD2GL to address above two issues. Specifically, we design a novel and effective non-key-value data structure, termed samtree, for dynamic topology storage, which largely reduces the memory cost. In addition, we propose an efficient sampling indexing structure FSTable by utilizing Fenwick tree, guaranteeing the efficiency of both dynamic updates and weighted sampling. Comprehensive experiments have demonstrated that, for dynamic updating the graph topology, the efficiency of our system by up to 79.8% and by up to 6.3 times in terms of memory and time cost, respectively. Now, our system serves the major traffic in WeChat Platform for training various GNN models.

This paper proposes Makex (MAKE senSE), a logic approach to explaining why a GNN-based model M ( x, y ) recommends item y to user x. It proposes a class of Rules for ExPlanations, denoted as REPs and defined with a graph pattern Q and dependency X → M ( x, y ), where X is a collection of predicates, and the model M ( x, y ) is treated as the consequence of the rule. Intuitively, given M ( x, y ), we discover pattern Q to identify relevant topology, and precondition X to disclose correlations, interactions and dependencies of vertex features; together they provide rationals behind prediction M ( x, y ), identifying what features are decisive for M to make predictions and under what conditions the decision can be made. We (a) define REPs with 1-WL test, on which most GNN models for recommendation are based; (b) develop an algorithm for discovering REPs for M as global explanations, and (c) provide a top- k algorithm to compute top-ranked local explanations. Using real-life graphs, we empirically verify that Makex outperforms previous explanation methods in terms of fidelity, sparsity and efficiency.

Given a source node$s$and a target node$t$, the hitting probability tells us how likely an$\alpha$-terminating random walk (which stops with probability$\alpha$at each step) starting from$s$can hit$t$before it stops. This concept originates from the hitting time, a classic concept in random walks. In this paper, we focus on the group hitting probability (GHP) where the target is a set of nodes, measuring the node-to-group structural proximity. For this group version of the hitting probability, we present efficient algorithms for two types of GHP queries: the pairwise query which returns the GHP value of a target set$T$with respect to (w.r.t.) a source node$s$, and the top-$k$query which returns the top-$k$target sets with the largest GHP value w.r.t. a source node$s$. We first develop an efficient algorithm named SAMBA for the pairwise query, which is built on a group local push algorithm tailored for GHP, with rigorous analysis for correctness. Next, we show how to speed up SAMBA by combining the group local push algorithm with the Monte Carlo approach, where GHP brings new challenges as it might need to consider every hop of the random walk. We tackle this issue with a new formulation of the GHP and show how to provide approximation guarantees with a detailed theoretical analysis. With SAMBA as the backbone, we develop an iterative algorithm for top-$k$queries, which adaptively refines the bounds for the candidate target sets, and terminates as soon as it meets the stopping condition, thus saving unnecessary computational costs. We further present an optimization technique to accelerate the top-$k$query, improving its practical performance. Extensive experiments show that our solutions are orders of magnitude faster than their competitors.

Recently, cross-domain recommendation (CDR) has been widely studied in both research and industry since it can alleviate a long-standing challenge of traditional recommendation methods, i.e., data sparsity issue, by transferring the information from a relatively richer domain (termed source domain) to a sparser domain (termed target domain). To our best knowledge, most (if not all) existing CDR methods focus on transferring either the similar content information or the user preferences embedding from the source domain to the target domain. However, they fail to improve the recommendation performance in real-world recommendation scenarios where the items in the source domain are totally different from those in the target domain in terms of attributes. To solve the above issues, we analyzed the historical interactions of users from different domains in the WeChat platform, and found that if two users have similar interests (interactions) in one domain, they are very likely to have similar interests in another domain even though the items of these two domains are totally different in terms of attributes. Based on this observation, in this paper, we propose a novel model named Dual Interests-Aligned Graph Auto-Encoders (DIAGAE) by utilizing the inter-domain interest alignment of users. Besides, our proposed model DIAGAE also leverages graph decoding objectives to align intra-domain user interests, which makes the representation of two users who have similar interests in a single domain closer. Comprehensive experimental results demonstrate that our model DIAGAE outperforms state-of-the-art methods on both public benchmark datasets and online A/B tests in WeChat live-stream recommendation scenario. Our model DIAGAE now serves the major online traffic in WeChat live-streaming recommendation scenario.

Image retrieval keeps attracting a lot of attention from both academic and industry over past years due to its variety of useful applications. Due to the rapid growth of deep learning approaches, more better feature vectors of images could be discovered for improving image retrieval. However, most (if not all) existing deep learning approaches consider the similarity between two images locally without considering the similarity among a group of similar images globally , and thus could not return accurate results. In this article, we study the image retrieval with manifold ranking (MR) which considers both the local similarity and the global similarity, which could give more accurate results. However, existing best-known algorithms have one of the following issues: (1) they require to build a bulky index, (2) some of them do not have any theoretical bound on the output, and (3) some of them are time-consuming. Motivated by this, we propose two algorithms, namely Monte Carlo-based MR ( MCMR ) and MCMR+ , for image retrieval, which do not have the above issues. We are the first one to propose an index-free manifold ranking image retrieval with the output theoretical bound. More importantly, our algorithms give the first best-known time complexity result of \(O(n \log n)\) where \(n\) is the total number of images in the database compared with the existing best-known result of \(O(n^2)\) in the literature of computing the exact top- \(k\) results with quality guarantee. Lastly, our experimental result shows that MCMR+ outperforms existing algorithms by up to four orders of magnitude in terms of query time.

Recently, graph neural network (GNN) approaches have received huge interests in recommendation tasks due to their ability of learning more effective user and item representations. However, existing GNN-based recommendation models cannot support real-time recommendation where the model keeps its freshness by continuously training the streaming data that users produced, leading to negative impact on recommendation performance. To fully support graph-enhanced large-scale recommendation in real-time scenarios, a deep graph learning system is required to dynamically store the streaming data as a graph structure and enable the development of any GNN model incorporated with the capabilities of real-time training and online inference. However, such requirements rule out existing deep graph learning solutions. In this paper, we propose a new deep graph learning system called PlatoGL, where (1) an effective block-based graph storage is designed with non-trivial insertion/deletion mechanism for updating the graph topology in-milliseconds, (2) a non-trivial multi-blocks neighbour sampling method is proposed for efficient graph query, and (3) a cache technique is exploited to improve the storage stability. We have deployed PlatoGL in Wechat, and leveraged its capability in various content recommendation scenarios including live-streaming, article and micro-video. Comprehensive experiments on both deployment performance and benchmark performance~(w.r.t. its key features) demonstrate its effectiveness and scalability. One real-time GNN-based model, developed with PlatoGL, now serves the major online traffic in WeChat live-streaming recommendation scenario.

Due to the prevalence of graph data, graph analysis is very important nowadays. One popular analysis on graph data is Random Walk with Restart (RWR) since it provides a good metric for measuring the proximity of two nodes in a graph. Although RWR is important, it is challenging to design an algorithm for RWR. To the best of our knowledge, there are no existing RWR algorithms which, at the same time, (1) are index-free, (2) return answers with a theoretical guarantee and (3) are efficient. Motivated by this, in this paper, we propose an index-free algorithm called Residue-Accumulated approach (ResAcc) which returns answers with a theoretical guarantee efficiently. Our experimental evaluations on large-scale real graphs show that ResAcc is up to 4 times faster than the best-known previous algorithm, guaranteeing the same accuracy. Under typical settings, the best-known algorithm ran around 1000 seconds on a large dataset containing 41.7 million nodes, which is too time-consuming, while ResAcc finished in 275 seconds with the same accuracy. Moreover, ResAcc is up to 6 orders of magnitude more accurate than the best-known algorithm in practice with the same execution time, which is considered as a substantial improvement.

Image retrieval keeps attracting a lot of attention from both academic and industry over past years due to its variety of useful applications. Due to the rapid growth of deep learning approaches, more better feature vectors of images could be discovered for improving image retrieval. However, most (if not all) existing deep learning approaches consider the similarity between 2 images locally without considering the similarity among a group of similar images globally, and thus could not return accurate results. In this paper, we study the image retrieval with manifold ranking (MR) which considers both the local similarity and the global similarity, which could give more accurate results. However, existing best-known algorithms have one of the following issues: (1) They require a bulky index, (2) some of them do not have any theoretical bound on the output, and (3) some of them are time-consuming. Motivated by this, we propose an algorithm, namely Monte Carlo-based MR (MCMR) for image retrieval, which does not have the above issues. We are the first one to propose an index-free manifold ranking-based image retrieval with the output theoretical bound. Lastly, our experiments show that MCMR outperforms existing algorithms by up to 4 orders of magnitude in terms of query time.