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.

Abstract In heterogeneous graphs (HGs), which offer richer network and semantic insights compared to homogeneous graphs, the Metapath technique serves as an essential tool for data mining. This technique facilitates the specification of sequences of entity connections, elucidating the semantic composite relationships between various node types for a range of downstream tasks. Nevertheless, selecting the most appropriate metapath from a pool of candidates and assessing its impact presents significant challenges. To address this issue, our study introduces MetapathVis, an interactive visual analytics system designed to assist machine learning (ML) practitioners in comprehensively understanding and comparing the effects of metapaths from multiple fine‐grained perspectives. MetapathVis allows for an in‐depth evaluation of various models generated with different metapaths, aligning HG network information at the individual level with model metrics. It also facilitates the tracking of aggregation processes associated with different metapaths. The effectiveness of our approach is validated through three case studies and a user study, with feedback from domain experts confirming that our system significantly aids ML practitioners in evaluating and comprehending the viability of different metapath designs.

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.

In recent years, there are more and more attacks and exploitation aiming at network security vulnerabilities. It is effective for us to prevent criminals from exploiting vulnerabilities for attacks and help security analysts maintain equipment security that knows vulnerabilities and threats on time. With the knowledge graph, we can organize, manage, and utilize the massive information effectively in cyberspace. In this paper we construct the vulnerability ontology after analyzing multi-source heterogeneous databases. And the vulnerability knowledge graph is established. Experimental results show that the accuracy of entity recognition for extracting vendor names reaches 89.76%. The more rules used in entity recognition, the higher the accuracy and the lower the error rate.

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.

The performance of multiple input multiple output (MIMO) wireless networks is limited mainly by concurrent interference among sensor nodes. Effective link scheduling algorithms with the technology of successive interference cancellation (SIC) can maximize throughput in MIMO wireless networks. Most previous works on link scheduling in MIMO wireless networks did not consider SIC. In this paper, we propose a MIMO-SIC (MSIC) algorithm under the SINR model. First, a mathematical framework is established for the cross-layer optimization of routing and scheduling, with constraints of traffic balance and link capacity. Second, the interference regions are divided to characterize the level of interference between links. Finally, we propose a distributed link scheduling algorithm based on MSIC to eliminate the interference between competing links in the MIMO network. Experimental results show that the MSIC algorithm can increase the end-to-end throughput per unit by approximately 73% on average compared with non-SIC algorithms.