The annual ACM SIGKDD Conference on Knowledge Discover and Data Mining, the premier interdisciplinary conference in data science, runs Aug. 22 – 27 virtually due to the COVID-19 pandemic. As a dual-track conference, KDD 2020 has accepted 216 papers out of 1279 submissions in research track (16.9%) and 121 papers out of 756 submissions in applied data science track (16.0%).

Baidu has had 10 papers accepted at KDD 2020, covering a wide range of topics like knowledge graph, human-machine interaction, and anti-pandemic technologies. You can learn more about our work being presented in the list below.

1. Understanding the Impact of the COVID-19 Pandemic on Transportation-related Behaviors with Human Mobility Data

Jizhou Huang, Haifeng Wang, Miao Fan, An Zhuo, Yibo Sun, Ying Li

The constrained outbreak of COVID-19 in Mainland China has recently been regarded as a successful example of fighting this highly contagious virus. Both the short period (in about three months) of transmission and the sub-exponential increase of confirmed cases in Mainland China have proved that the Chinese authorities took effective epidemic prevention measures, such as case isolation, travel restrictions, closing recreational venues, and banning public gatherings. These measures can, of course, effectively control the spread of the COVID-19 pandemic. Meanwhile, they may dramatically change the human mobility patterns, such as the daily transportation-related behaviors of the public. To better understand the impact of COVID-19 on transportation-related behaviors and to provide more targeted anti-epidemic measures, we use the huge amount of human mobility data collected from Baidu Maps, a widely-used Web mapping service in China, to look into the detail reaction of the people there during the pandemic. To be specific, we conduct data-driven analysis on transportation- related behaviors during the pandemic from the perspectives of 1) means of transportation, 2) type of visited venues, 3) check-in time of venues, 4) preference on “origin-destination” distance, and 5) “origin-transportation-destination” patterns. For each topic, we also give our specific insights and policy-making suggestions. Given that the COVID-19 pandemic is still spreading in more than 200 countries and territories worldwide, infecting millions of people, the insights and suggestions provided here may help fight COVID-19.

Paper: https://dl.acm.org/doi/10.1145/3394486.3412856

2. Personalized Prefix Embedding for POI Auto-Completion in the Search Engine of Baidu Maps

Jizhou Huang; Haifeng Wang; Miao Fan; An Zhuo; Ying Li

Point of interest auto-completion (POI-AC) is a featured function in the search engine of many Web mapping services. This function keeps suggesting a dynamic list of POIs as a user types each character, and it can dramatically save the effort of typing, which is quite useful on mobile devices. Existing approaches on POI-AC for industrial use mainly adopt various learning to rank (LTR) models with handcrafted features and even historically clicked POIs are taken into account for personalization. However, these prior arts tend to reach performance bottlenecks as both heuristic features and search history of users cannot directly model personal input habits. In this paper, we present an end-to-end neural-based framework for POI-AC, which has been recently deployed in the search engine of Baidu Maps, one of the largest Web mapping applications with hundreds of millions monthly active users worldwide. In order to establish connections among users, their personal input habits, and correspondingly interested POIs, the proposed framework (abbr. P3AC) is composed of three components, i.e., a multi-layer Bi-LSTM network to adapt to personalized prefixes, a CNN-based network to model multi-sourced information on POIs, and a triplet ranking loss function to optimize both personalized prefix embeddings and distributed representations of POIs. We first use large-scale real-world search logs of Baidu Maps to assess the performance of P3AC offline measured by multiple metrics, including Mean Reciprocal Rank (MRR), Success Rate (SR), and normalized Discounted Cumulative Gain (nDCG). Extensive experimental results demonstrate that it can achieve substantial improvements. Then we decide to launch it online and observe that some other critical indicators on user satisfaction, such as the average number of keystrokes and the average typing speed at keystrokes in a POI-AC session, which significantly decrease as well. In addition, we have released both the source codes of P3AC and the experimental data to the public for reproducibility tests.

Paper:https://dl.acm.org/doi/10.1145/3394486.3403318

3. ConSTGAT: Contextual Spatial-Temporal Graph Attention Network for Travel Time Estimation at Baidu Maps

Xiaomin Fang; Jizhou Huang; Fan Wang; Lingke Zeng; Haijin Liang; Haifeng Wang

The task of travel time estimation (TTE), which estimates the travel time for a given route and departure time, plays an important role in intelligent transportation systems such as navigation, route planning, and ride-hailing services. This task is challenging because of many essential aspects, such as traffic prediction and contextual information. First, the accuracy of traffic prediction is strongly correlated with the traffic speed of the road segments in a route. Existing work mainly adopts spatial-temporal graph neural networks to improve the accuracy of traffic prediction, where spatial and temporal information is used separately. However, one drawback is that the spatial and temporal correlations are not fully exploited to obtain better accuracy. Second, contextual information of a route, i.e., the connections of adjacent road segments in the route, is an essential factor that impacts the driving speed. Previous work mainly uses sequential encoding models to address this issue. However, it is difficult to scale up sequential models to large-scale real-world services. In this paper, we propose an end-to-end neural framework named ConSTGAT, which integrates traffic prediction and contextual information to address these two problems. Specifically, we first propose a spatial-temporal graph neural network that adopts a novel graph attention mechanism, which is designed to fully exploit the joint relations of spatial and temporal information. Then, in order to efficiently take advantage of the contextual information, we design a computationally efficient model that applies convolutions over local windows to capture a route’s contextual information and further employs multi-task learning to improve the performance. In this way, the travel time of each road segment can be computed in parallel and in advance. Extensive experiments conducted on large-scale real-world datasets demonstrate the superiority of ConSTGAT. In addition, ConSTGAT has already been deployed in production at Baidu Maps, and it successfully keeps serving tens of billions of requests every day. This confirms that ConSTGAT is a practical and robust solution for large-scale real-world TTE services.

Paper:https://dl.acm.org/doi/10.1145/3394486.3403320

4. Combo-Attention Network for Baidu Video Advertising

Tan Yu; Yi Yang; Yi Li; Xiaodong Chen; Mingming Sun; Ping Li

With the progress of communication technology and the popularity of the smart phone, videos grow to be the largest medium. Since videos can grab a customer’s attention quickly and leave a big impression, video ads can gain more trust than traditional ads. Thus advertisers start to pour more resources into making creative video ads to built the connections with potential customers. Baidu, as the leading search engine company in China, receives billions of search queries per day. In this paper, we introduce a technique used in Baidu video advertising for feeding relevant video ads according to the user’s query. Note that, retrieving relevant videos using the text query is a cross-modal problem. Due to the modal gap, the text-to-video search is more challenging than well exploited text-to-text search and image-to-image search. To tackle this challenge, we propose a Combo-Attention Network (CAN) and launch it in Baidu video advertising. In the proposed CAN model, we represent a video as a set of bounding boxes features and represent a sentence as a set of words features, and formulate the sentence-to-video search as a set-to-set matching problem. The proposed CAN is built upon the proposed combo-attention module, which exploits cross-modal attentions besides self attentions to effectively capture the relevance between words and bounding boxes. To testify the effectiveness of the proposed CAN offline, we built a Daily700K dataset collected from HaoKan APP. The systematic experiments on Daily700K as well as a public dataset, VATEX, demonstrate the effectiveness of our CAN. After launching the proposed CAN in Baidu’s dynamic video advertising (DVA), we achieve a $5.47%$ increase in Conversion Rate (CVR) and a $11.69%$ increase in advertisement impression rate.

Paper: https://www.kdd.org/kdd2020/accepted-papers/view/combo-attention-network-for-baidu-video-advertising

5. Intelligent Exploration for User Interface Modules of Mobile App with Collective Learning

Jingbo Zhou; Zhenwei Tang; Min Zhao; Xiang Ge; Fuzheng Zhuang; Meng Zhou; Liming Zou; Chenglei Yang; Hui Xiong

A mobile app interface usually consists of a set of user interface modules. How to properly design these user interface modules is vital to achieving user satisfaction for a mobile app. However, there are few methods to determine design variables for user interface modules except for relying on the judgment of designers. Usually, a laborious post-processing step is necessary to verify the key change of each design variable. Therefore, there is an only very limited amount of design solutions that can be tested. It is time- consuming and almost impossible to figure out the best design solutions as there are many modules. To this end, we introduce FEELER, a framework to fast and intelligently explore design solutions of user interface modules with a collective machine learning approach. FEELER can help designers quantitatively measure the preference score of different design solutions, aiming to facilitate the designers to conveniently and quickly adjust user interface module. We conducted extensive experimental evaluations on two real-life datasets to demonstrate its applicability in real-life cases of user interface module design in the Baidu App, which is one of the most popular mobile apps in China.

Paper:http://zhoujingbo.github.io/paper/kdd2020_intelligent_zhou.pdf

6. Polestar: An Intelligent, Efficient and National-Wide Public Transportation Routing Engine

Hao Liu; Ying Li; Yanjie Fu; Huaibo Mei; Jingbo Zhou; Xu Ma; Hui Xiong

Public transportation plays a critical role in people's daily life. It has been proven that public transportation is more environmentally sustainable, efficient, and economical than any other forms of travel. However, due to the increasing expansion of transportation networks and more complex travel situations, people are having difficulties in efficiently finding the most preferred route from one place to another through public transportation systems. To this end, in this paper, we present Polestar, a data-driven engine for intelligent and efficient public transportation routing. Specifically, we first propose a novel Public Transportation Graph (PTG) to model public transportation system in terms of various travel costs, such as time or distance. Then, we introduce a general route search algorithm coupled with an efficient station binding method for efficient route candidate generation. After that, we propose a two-pass route candidate ranking module to capture user preferences under dynamic travel situations. Finally, experiments on two real-world data sets demonstrate the advantages of Polestar in terms of both efficiency and effectiveness. Indeed, in early 2019, Polestar has been deployed on Baidu Maps, one of the world's largest map services. To date, Polestar is servicing over 330 cities, answers over a hundred million of queries each day, and achieves substantial improvement of user click ratio.

Paper: https://arxiv.org/abs/2007.07195

7. Geodemographic Influence Maximization

Kaichen Zhang; Jingbo Zhou; Donglai Tao; Panagiotis Karras; Qing Li; Hui Xiong

Given a set of locations in a city, on which ones should we place ads on so as to reach as many people as possible within a limited budget? Past research has addressed this question under the as- sumption that dense trajectory data are available to determine the reach of each ad. However, the data that are available in most in- dustrial settings do not consist of dense, long-range trajectories; instead, they consist of statistics on people’s short-range point-to- point movements. In this paper, we address the natural problem that arises on such data: given a distribution of population and point-to-point movement statistics over a network, find a set of locations within a budget that achieves maximum expected reach. We call this problem geodemographic influence maximization (GIM). We show that the problem is NP-hard, but its objective function is monotone and submodular, thus admits a greedy algorithm with a 11 (1 − ) approximation ratio. Still, this algorithm is inapplicable on 2e large-scale data for high-frequency digital signage ads. We develop an efficient deterministic algorithm, Lazy-Sower, exploiting a novel, tight double-bounding scheme of marginal influence gain as well as the locality proprieties of the problem; a learning-based vari- ant, NN-Sower, utilizes randomization and deep learning to further improve efficiency, with a slight loss of quality. Our exhaustive experimental study on two real-world urban datasets demonstrates the efficacy and efficiency of our solutions compared to baselines.

Paper: http://zhoujingbo.github.io/paper/kdd2020_geodemographic_zhang.pdf

8. Competitive Analysis for Points of Interest

Shuangli Li; Jingbo Zhou; Hao Liu; Xinjiang Lu; Tong Xu; Hui Xiong

The competitive relationship of Points of Interest (POIs) refers to the degree of competition between two POIs for business opportunities from third parties in an urban area. Existing studies for competitive analysis usually focus on mining competitive relationships of entities, such as companies or products, from textual data. However, there are few studies which have a focus on competitive analysis for POIs. Indeed, the growing availability of user behavior data about POIs, such as POI reviews and human mobility data, enables a new paradigm for understanding the competitive relationships among POIs. To this end, in this paper, we study how to predict the POI competitive relationship. Along this line, a very first challenge is how to integrate heterogeneous user behavior data with the spatial features of POIs. As a solution, we first build a heterogeneous POI information network (HPIN) from POI reviews and map search data. Then, we develop a graph neural network-based deep learning framework, named DeepR, for POI competitive relationship prediction based on HPIN. Specifically, DeepR contains two components: a spatial adaptive graph neural network (SA-GNN) and a POI pairwise knowledge extraction learning (PKE) model. The SA-GNN is a novel GNN architecture with incorporating POI’s spatial in- formation and location distribution by a specially designed spatial oriented aggregation layer and spatial-dependency attentive propagation mechanism. In addition, PKE is devised to distill the POI pairwise knowledge in HPIN being useful for relationship prediction into condensate vectors with relational graph convolution and cross attention. Finally, extensive experiments on two real-world datasets demonstrate the effectiveness of our method.

Paper:http://zhoujingbo.github.io/paper/kdd2020_competitive_li.pdf

9. Local Community Detection in Multiple Networks

Dongsheng Luo; Yuchen Bian; Yaowei Yan; Xiao Liu; Jun Huan; Xiang Zhang

Local community detection aims to find a set of densely-connected nodes containing given query nodes. Most existing local community detection methods are designed for a single network. However, a single network can be noisy and incomplete. Multiple networks are more informative in real-world applications. There are multiple types of nodes and multiple types of node proximities. Complementary information from different networks helps to improve detection accuracy. In this paper, we propose a novel RWM (Random Walk in Multiple networks) model to find relevant local communities in all networks for a given query node set from one network. RWM sends a random walker in each network to obtain the local proximity w.r.t. the query nodes (i.e., node visiting probabilities). Walkers with similar visiting probabilities reinforce each other. They restrict the probability propagation around the query nodes to identify relevant subgraphs in each network and disregard irrelevant parts. We provide rigorous theoretical foundations for RWM and develop two speeding-up strategies with performance guarantees. Comprehensive experiments are conducted on synthetic and real-world datasets to evaluate the effectiveness and efficiency of RWM.

Paper: http://personal.psu.edu/dul262/RWM/RWM.pdf

GitHub:https://github.com/flyingdoog/RWM

10. Dual Channel Hypergraph Collaborative Filtering

Shuyi Ji; Yifan Feng; Rongrong Ji; Xibin Zhao; Wanwan Tang; Yue Gao

Collaborative filtering (CF) is one of the most popular and important recommendation methodologies in the heart of numerous recommender systems today. Although widely adopted, existing CF-based methods, ranging from matrix factorization to the emerging graph-based methods, suffer inferior performance especially when the data for training are very limited. In this paper, we first pinpoint the root causes of such deficiency and observe two main disadvantages that stem from the inherent designs of existing CF-based methods, i.e., 1) inflexible modeling of users and items and 2) insufficient modeling of high-order correlations among the subjects. Under such circumstances, we propose a dual channel hypergraph collaborative filtering (DHCF) framework to tackle the above issues. First, a dual channel learning strategy, which holistically leverages the divide-and-conquer strategy, is introduced to learn the representation of users and items so that these two types of data can be elegantly interconnected while still maintaining their specific properties. Second, the hypergraph structure is employed for modeling users and items with explicit hybrid high-order correlations. The jump hypergraph convolution (JHConv) method is proposed to support the explicit and efficient embedding propagation of high-order correlations. Comprehensive experiments on two public benchmarks and two new real-world datasets demonstrate that DHCF can achieve significant and consistent improvements against other state-of-the-art methods.