OpenRaiser/Intern-Atlas huggingface dataset:
On the Knowledge-Driven Analytics and Systems Impacting Human Quality of Life
Authors: Arijit Ukil, Leandro Marín, Antonio Jara, John R. Farserotu
Venue: CIKM
Year: 2020

The present scenario of Covid-19 pandemic has disrupted the human life to a larger extent. In such context, human-centric applications and systems that endeavor to positively impact the human quality of life is of utmost importance. Knowledge-driven analytics that help to build such intelligent systems play important role to construct the required eco-system on the macro-scale. It is worth mentioning that Knowledge-Driven Analytics and Systems Impacting Human Quality of Life (KDAH) workshop in ACM International Conference on Information and Knowledge Management (CIKM), attempts to bring out the intricate research direction for enabling a sustainable human society through the positive co-existence of human beings and intelligent systems.
When Inverse Propensity Scoring does not Work: Affine Corrections for Unbiased Learning to Rank
Authors: Ali Vardasbi, Harrie Oosterhuis, Maarten de Rijke
Venue: CIKM
Year: 2020

Besides position bias, which has been well-studied, trust bias is another type of bias prevalent in user interactions with rankings: users are more likely to click incorrectly w.r.t. their preferences on highly ranked items because they trust the ranking system. While previous work has observed this behavior in users, we prove that existing Counterfactual Learning to Rank (CLTR) methods do not remove this bias, including methods specifically designed to mitigate this type of bias. Moreover, we prove that Inverse Propensity Scoring (IPS) is principally unable to correct for trust bias under non-trivial circumstances. Our main contribution is a new estimator based on affine corrections: it both reweights clicks and penalizes items displayed on ranks with high trust bias. Our estimator is the first estimator that is proven to remove the effect of both trust bias and position bias. Furthermore, we show that our estimator is a generalization of the existing (CLTR) framework: if no trust bias is present, it reduces to the original (IPS) estimator. Our semi-synthetic experiments indicate that by removing the effect of trust bias in addition to position bias, (CLTR) can approximate the optimal ranking system even closer than previously possible.
LiFT: A Scalable Framework for Measuring Fairness in ML Applications
Authors: Sriram Vasudevan, Krishnaram Kenthapadi
Venue: CIKM
Year: 2020

Many internet applications are powered by machine learned models, which are usually trained on labeled datasets obtained through user feedback signals or human judgments. Since societal biases may be present in the generation of such datasets, it is possible for the trained models to be biased, thereby resulting in potential discrimination and harms for disadvantaged groups. Motivated by the need to understand and address algorithmic bias in web-scale ML systems and the limitations of existing fairness toolkits, we present the LinkedIn Fairness Toolkit (LiFT), a framework for scalable computation of fairness metrics as part of large ML systems. We highlight the key requirements in deployed settings, and present the design of our fairness measurement system. We discuss the challenges encountered in incorporating fairness tools in practice and the lessons learned during deployment at LinkedIn. Finally, we provide open problems based on practical experience.
A Graph Matching Attack on Privacy-Preserving Record Linkage
Authors: Anushka Vidanage, Peter Christen, Thilina Ranbaduge, Rainer Schnell
Venue: CIKM
Year: 2020

To facilitate advanced analytics, data science projects increasingly require records about individuals to be linked across databases. Generally no unique entity identifiers are available in the databases to be linked, and therefore quasi-identifiers such as names, addresses, and dates of birth are used to link records. The process of linking records without revealing any sensitive or confidential information about the entities represented by these records is known as privacy-preserving record linkage (PPRL). Various encoding and encryption based PPRL methods have been developed in the past two decades. Most existing PPRL methods calculate approximate similarities between records because errors and variations can occur in quasi-identifying attribute values. Even though being used in real-world linkage applications, certain PPRL methods, such as popular Bloom filter encoding, have shown to be vulnerable to cryptanalysis attacks. In this paper we present a novel attack on PPRL methods that exploits the approximate similarities calculated between encoded records. Our attack matches nodes in a similarity graph generated from an encoded database with a corresponding similarity graph generated from a plain-text database to re-identify sensitive values. Our attack is not limited to any specific PPRL method, and in an experimental evaluation we apply it on three PPRL encoding methods using three different databases. This evaluation shows that our attack can successfully re-identify sensitive values from these encodings with high accuracy where no previous attack on PPRL would have been successful.
Semi-Supervised Max-Sum Clustering
Authors: Konstantin Voevodski
Venue: CIKM
Year: 2020

We study max-sum clustering in a semi-supervised setting. Our objective function maximizes the pairwise within-cluster similarity with respect to some null hypothesis regarding the similarity. This is a natural objective that does not require any additional parameters, and is a generalization of the well-known modularity objective function. We show that for such an objective function in a semi-supervised setting we can compute an additive approximation of the optimal solution in the general case, and a constant-factor approximation when the optimal objective value is large. The supervision that we consider is in the form of cluster assignment queries and same-cluster queries; we also study the setting where the query responses are noisy. Our algorithm also generalizes to the min-sum objective function, for which we can achieve similar performance guarantees. We present computational experiments to show that our framework is effective for clustering text data - we are able to find clusterings that are close to the queried clustering and have a good objective value.
Denoising Individual Bias for Fairer Binary Submatrix Detection
Authors: Changlin Wan, Wennan Chang, Tong Zhao, Sha Cao, Chi Zhang
Venue: CIKM
Year: 2020

Low rank representation of binary matrix is powerful in disentangling sparse individual-attribute associations, and has received wide applications. Existing binary matrix factorization (BMF) or co-clustering (CC) methods often assume i.i.d background noise. However, this assumption could be easily violated in real data, where heterogeneous row- or column-wise probability of binary entries results in disparate element-wise background distribution, and paralyzes the rationality of existing methods. We propose a binary data denoising framework, namely BIND, which optimizes the detection of true patterns by estimating the row- or column-wise mixture distribution of patterns and disparate background, and eliminating the binary attributes that are more likely from the background. BIND is supported by thoroughly derived mathematical property of the row- and column-wise mixture distributions. Our experiment on synthetic and real-world data demonstrated BIND effectively removes background noise and drastically increases the fairness and accuracy of state-of-the arts BMF and CC methods.
Soap: Soaking Capacity Optimization for Multi-Document Summarization
Authors: Kexiang Wang, Baobao Chang, Zhifang Sui
Venue: CIKM
Year: 2020

Multi-document summarization (MDS) aims at giving a brief summary for a cluster of related documents. In this paper, we consider the MDS task as an optimization problem with a novel measure named soaking capacity being the objective function. The origin of our method is the classic hypothesis: the summary components are the sinks of information diffusion. We point out that the hypothesis only gives the role of summary but does not cover how well a summary acts as this role. To fill in the gap, soaking capacity is formally defined to quantify the ability of summary to soak up information. We explicitly demonstrate its fitness as an indicator for both the saliency and the diversity goal of MDS. For solving the optimization problem, we propose a greedy algorithm named Soap by adopting a surrogate of soaking capacity to accelerate the computation. Experiments on MDS datasets across various domains show the great potential of Soap as compared with the state-of-the-art MDS systems.
Efficient Neural Query Auto Completion
Authors: Sida Wang, Weiwei Guo, Huiji Gao, Bo Long
Venue: CIKM
Year: 2020

Query Auto Completion (QAC), as the starting point of information retrieval tasks, is critical to user experience. Generally it has two steps: generating completed query candidates according to query prefixes, and ranking them based on extracted features. Three major challenges are observed for a query auto completion system: (1) QAC has a strict online latency requirement. For each keystroke, results must be returned within tens of milliseconds, which poses a significant challenge in designing sophisticated language models for it. (2) For unseen queries, generated candidates are of poor quality as contextual information is not fully utilized. (3) Traditional QAC systems heavily rely on handcrafted features such as the query candidate frequency in search logs, lacking sufficient semantic understanding of the candidate. In this paper, we propose an efficient neural QAC system with effective context modeling to overcome these challenges. On the candidate generation side, this system uses as much information as possible in unseen prefixes to generate relevant candidates, increasing the recall by a large margin. On the candidate ranking side, an unnormalized language model is proposed, which effectively captures deep semantics of queries. This approach presents better ranking performance over state-of-the-art neural ranking methods and reduces ~95% latency compared to neural language modeling methods. The empirical results on public datasets show that our model achieves a good balance between accuracy and efficiency. This system is served in LinkedIn job search with significant product impact observed.
Graph Few-shot Learning with Attribute Matching
Authors: Ning Wang, Minnan Luo, Kaize Ding, Lingling Zhang, Jundong Li, Qinghua Zheng
Venue: CIKM
Year: 2020

Due to the expensive cost of data annotation, few-shot learning has attracted increasing research interests in recent years. Various meta-learning approaches have been proposed to tackle this problem and have become the de facto practice. However, most of the existing approaches along this line mainly focus on image and text data in the Euclidean domain. However, in many real-world scenarios, a vast amount of data can be represented as attributed networks defined in the non-Euclidean domain, and the few-shot learning studies in such structured data have largely remained nascent. Although some recent studies have tried to combine meta-learning with graph neural networks to enable few-shot learning on attributed networks, they fail to account for the unique properties of attributed networks when creating diverse tasks in the meta-training phase---the feature distributions of different tasks could be quite different as instances (i.e., nodes) do not follow the data i.i.d. assumption on attributed networks. Hence, it may inevitably result in suboptimal performance in the meta-testing phase. To tackle the aforementioned problem, we propose a novel graph meta-learning framework--Attribute Matching Meta-learning Graph Neural Networks (AMM-GNN). Specifically, the proposed AMM-GNN leverages an attribute-level attention mechanism to capture the distinct information of each task and thus learns more effective transferable knowledge for meta-learning. We conduct extensive experiments on real-world datasets under a wide range of settings and the experimental results demonstrate the effectiveness of the proposed AMM-GNN framework.
Match Tracing: A Unified Framework for Real-time Win Prediction and Quantifiable Performance Evaluation
Authors: Kai Wang, Hao Li, Linxia Gong, Jianrong Tao, Runze Wu, Changjie Fan, Liang Chen, Peng Cui
Venue: CIKM
Year: 2020

Win prediction and performance evaluation are two core subjects in the sport analytics. Traditionally, they are treated separately and studied by two independent communities. However, this is not the intuitive way how humans interpret the matches: we predict the match results with the competition carrying on, and simultaneously evaluate each action based on the game context and its downstream impact. Predicting the match outcomes and evaluating the actions are coupled tasks, and the more accurately we predict, the better the evaluation is To this end, we develop a unified Match Tracing framework (namely, MT), for tackling the win prediction and performance evaluation jointly. The main idea of MT is to learn a real-time look-ahead win rate curve rather than a single scalar (win or lose). And the value of an action can be objectively measured with respect to the increase or decrease of the curve. To meet the low-latency restrictions of the online deployments, an efficient model equipped with recurrent attention mechanism and matrix perturbation (i.e., MT-Net) is built for learning and yielding the win rate curve. MT-Net encodes the players' behavior sequence through an attention mechanism and captures the player-interaction effects through a graph embedding method. With the action values derived from the win rate curve, performance can be quantified at different granularities (action/player/match level) by integrated analysis. Experiments on an e-sport game demonstrate the prediction effectiveness and the feasibility of the MT framework. Furthermore, we present the detailed application cases of MT, including key actions recognition and close match detection.
Efficient Knowledge Graph Validation via Cross-Graph Representation Learning
Authors: Yaqing Wang, Fenglong Ma, Jing Gao
Venue: CIKM
Year: 2020

Recent advances in information extraction have motivated the automatic construction of huge Knowledge Graphs (KGs) by mining from large-scale text corpus. However, noisy facts are unavoidably introduced into KGs that could be caused by automatic extraction. To validate the correctness of facts (i.e., triplets) inside a KG, one possible approach is to map the triplets into vector representations by capturing the semantic meanings of facts. Although many representation learning approaches have been developed for knowledge graphs, these methods are not effective for validation. They usually assume that facts are correct, and thus may overfit noisy facts and fail to detect such facts. Towards effective KG validation, we propose to leverage an external human-curated KG as auxiliary information source to help detect the errors in a target KG. The external KG is built upon human-curated knowledge repositories and tends to have high precision. On the other hand, although the target KG built by information extraction from texts has low precision, it can cover new or domain-specific facts that are not in any human-curated repositories. To leverage external KG for validation, one intuitive approach is to find matched triplets between the target KG and the external KG. However, this approach can only apply to the small portion of triplets that are covered by both external and target KGs and is not useful for the validation of majority of the triplets. To tackle this challenging task, we propose a cross-graph representation learning framework, i.e., CrossVal, which can leverage an external KG to validate the facts in the target KG efficiently. This is achieved by embedding triplets based on their semantic meanings, drawing cross-KG negative samples and estimating a confidence score for each triplet based on its degree of correctness. We evaluate the proposed framework on datasets across different domains. Experimental results show that the proposed framework achieves the best performance compared with the state-of-the-art methods on large-scale KGs.
Bringing Order to Network Embedding: A Relative Ranking based Approach
Authors: Yaojing Wang, Guosheng Pan, Yuan Yao, Hanghang Tong, Hongxia Yang, Feng Xu, Jian Lu
Venue: CIKM
Year: 2020

Network embedding aims to automatically learn the node representations in networks. The basic idea of network embedding is to first construct a network to describe the neighborhood context for each node, and then learn the node representations by designing an objective function to preserve certain properties of the constructed context network. The vast majority of the existing methods, explicitly or implicitly, follow a pointwise design principle. That is, the objective can be decomposed into the summation of the certain goodness function over each individual edge of the context network. In this paper, we propose to go beyond such pointwise approaches, and introduce the ranking-oriented design principle for network embedding. The key idea is to decompose the overall objective function into the summation of a goodness function over a set of edges to collectively preserve their relative rankings on the context network. We instantiate the ranking-oriented design principle by two new network embedding algorithms, including a pairwise network embedding method PaWine which optimizes the relative weights of edge pairs, and a listwise method LiWine which optimizes the relative weights of edge lists. Both proposed algorithms bear a linear time complexity, making themselves scalable to large networks. We conduct extensive experimental evaluations on five real datasets with a variety of downstream learning tasks, which demonstrate that the proposed approaches consistently outperform the existing methods.
April: An Automatic Graph Data Management System Based on Reinforcement Learning
Authors: Hongzhi Wang, Zhixin Qi, Lei Zheng, Yun Feng, Junfei Ouyang, Haoqi Zhang, Xiangxi Zhang, Ziming Shen, Shirong Liu
Venue: CIKM
Year: 2020

The great amount and complex structure of graph data bring a big challenge to graph data management. However, traditional management approaches cannot tackle the challenge. Fortunately, reinforcement learning provides a new approach to solve this problem due to its automation and adaptivity in decision making. Motivated by this, we develop April, an automatic graph data management system, which performs storage structure selection, index selection, and query optimization based on reinforcement learning. The system selects storage structure, indices effectively and automatically, and optimizes the SPARQL queries efficiently. April also offers a friendly interface for users, which allows users to interact with the system in a customized mode. We demonstrate the effectiveness and efficiency of April with two graph data benchmarks.
Streaming Graph Neural Networks via Continual Learning
Authors: Junshan Wang, Guojie Song, Yi Wu, Liang Wang
Venue: CIKM
Year: 2020

Graph neural networks (GNNs) have achieved strong performance in various applications. In the real world, network data is usually formed in a streaming fashion. The distributions of patterns that refer to neighborhood information of nodes may shift over time. The GNN model needs to learn the new patterns that cannot yet be captured. But learning incrementally leads to the catastrophic forgetting problem that historical knowledge is overwritten by newly learned knowledge. Therefore, it is important to train GNN model to learn new patterns and maintain existing patterns simultaneously, which few works focus on. In this paper, we propose a streaming GNN model based on continual learning so that the model is trained incrementally and up-to-date node representations can be obtained at each time step. Firstly, we design an approximation algorithm to detect new coming patterns efficiently based on information propagation. Secondly, we combine two perspectives of data replaying and model regularization for existing pattern consolidation. Specially, a hierarchy-importance sampling strategy for nodes is designed and a weighted regularization term for GNN parameters is derived, achieving greater stability and generalization of knowledge consolidation. Our model is evaluated on real and synthetic data sets and compared with multiple baselines. The results of node classification prove that our model can efficiently update model parameters and achieve comparable performance to model retraining. In addition, we also conduct a case study on the synthetic data, and carry out some specific analysis for each part of our model, illustrating its ability to learn new knowledge and maintain existing knowledge from different perspectives.
DisenHAN: Disentangled Heterogeneous Graph Attention Network for Recommendation
Authors: Yifan Wang, Suyao Tang, Yuntong Lei, Weiping Song, Sheng Wang, Ming Zhang
Venue: CIKM
Year: 2020

Heterogeneous information network has been widely used to alleviate sparsity and cold start problems in recommender systems since it can model rich context information in user-item interactions. Graph neural network is able to encode this rich context information through propagation on the graph. However, existing heterogeneous graph neural networks neglect entanglement of the latent factors stemming from different aspects. Moreover, meta paths in existing approaches are simplified as connecting paths or side information between node pairs, overlooking the rich semantic information in the paths. In this paper, we propose a novel disentangled heterogeneous graph attention network DisenHAN for top-N recommendation, which learns disentangled user/item representations from different aspects in a heterogeneous information network. In particular, we use meta relations to decompose high-order connectivity between node pairs and propose a disentangled embedding propagation layer which can iteratively identify the major aspect of meta relations. Our model aggregates corresponding aspect features from each meta relation for the target user/item. With different layers of embedding propagation, DisenHAN is able to explicitly capture the collaborative filtering effect semantically. Extensive experiments on three real-world datasets show that DisenHAN consistently outperforms state-of-the-art approaches. We further demonstrate the effectiveness and interpretability of the learned disentangled representations via insightful case studies and visualization.