OpenRaiser/Intern-Atlas huggingface dataset:
Graph Neural Networks for the Global Economy with Microsoft DeepGraph
Authors: Jaewon Yang, Baoxu Shi, Alex Samylkin
Venue: WSDM
Year: 2022

Graph Neural Networks (GNNs) are AI models that learn embeddings for the nodes in a graph and use the embeddings to perform prediction tasks. In this talk, we present how we developed GNNs for the LinkedIn economic graph. LinkedIn economic graph is a digital representation of the global economy with 1B nodes and 200B edges, consisting of social graphs about members' connections, activity graphs between members and other economic entities, and knowledge graphs about members', companies', job postings' attributes. By applying GNN to this graph, we can utilize the full potential of the economic graph in many search and recommendation products across LinkedIn. The biggest challenge was to scale up GNNs to a massive scale of billion nodes and edges. To address this challenge, we developed Microsoft DeepGraph, an open source library for large scale GNN development. DeepGraph allows for training GNNs on large graphs by serving the graph in a distributed fashion with graph engine servers. In this talk, we will highlight the strengths of DeepGraph, such as support for both PyTorch and TensorFlow, and integration with Azure ML and Azure Kubernetes Service. We will share lessons and findings from developing GNNs for various applications around the LinkedIn economic graph. We will explain how we combine graphs such as social graph, activity graph, knowledge graphs into one gigantic heterogeneous graph, and what algorithms we employed for this heterogenous graph. We will present a few case studies, such as how we identify job postings with vague titles and replace them with more specific titles using GNNs.
Few-shot Link Prediction in Dynamic Networks
Authors: Cheng Yang, Chunchen Wang, Yuanfu Lu, Xumeng Gong, Chuan Shi, Wei Wang, Xu Zhang
Venue: WSDM
Year: 2022

Dynamic link prediction, which aims at forecasting future edges of a node in a dynamic network, is an important problem in network science and has a wide range of real-world applications. A key property of dynamic networks is that new nodes and links keep coming over time and these new nodes usually have only a few links at their arrivals. However, how to predict future links for these few-shot nodes in a dynamic network has not been well studied. Existing dynamic network representation learning methods were not specialized for few-shot scenarios and thus would lead to suboptimal performances. In this paper, we propose a novel model based on a meta-learning framework, dubbed as MetaDyGNN, for few-shot link prediction in dynamic networks. Specifically, we propose a meta-learner with hierarchical time interval-wise and node-wise adaptions to extract general knowledge behind this problem. We also design a simple and effective dynamic graph neural network (GNN) module to characterize the local structure of each node in meta-learning tasks. As a result, the learned general knowledge serves as model initializations, and can quickly adapt to new nodes with a fine-tuning process on only a few links. Experimental results show that our proposed MetaDyGNN significantly outperforms state-of-the-art methods on three publicly available datasets.
Interpretable Relation Learning on Heterogeneous Graphs
Authors: Qiang Yang, Qiannan Zhang, Chuxu Zhang, Xiangliang Zhang
Venue: WSDM
Year: 2022

Relation learning, widely used in recommendation systems or relevant entity search over knowledge graphs, has attracted increasing attentions in recent years. Existing methods like network embedding and graph neural networks (GNNs), learn the node representations from neighbors and calculate the similarity score for relation prediction. Despite effective prediction performance, they lack explanations to the predicted results. We propose a novel interpretable relation learning model named IRL, which can not only predict whether relations exist between node pairs, but also make the inference more transparent and convincing. Specifically, we introduce a meta-path based path encoder to model sequential dependency between nodes through recurrent neural network. We also apply the self-supervised GNN on the extracted sub-graph to capture the graph structure by aggregating information from neighbors, which are fed into the meta-path encoder. In addition, we propose a meta-path walk pruning strategy for positive path generation and an adaptive negative sampling method for negative path generation to improve the quality of paths, which both consider the semantics of nodes in the heterogeneous graph. We conduct extensive experiments on two public heterogeneous graph data, AMiner and Delve, for different relation prediction tasks, which demonstrate significant improvements of our model over the existing embedding-based and sequential modeling-based methods.
Fast Semantic Matching via Flexible Contextualized Interaction
Authors: Wenwen Ye, Yiding Liu, Lixin Zou, Hengyi Cai, Suqi Cheng, Shuaiqiang Wang, Dawei Yin
Venue: WSDM
Year: 2022

Deep pre-trained language models (e.g., BERT) lead to remarkable headway in many Natural Language Processing tasks. Their superior capacity in perceiving textual data is also witnessed in semantic matching tasks (e.g., question answering, web search). Particularly for matching a pair of query and text candidate, the current state-of-the-arts usually rely on the semantic representations produced by BERT, and compute relevance scores with various interaction (i.e., matching) methods. However, they may 1) miss fine-grained phrase-level interaction between the input query and candidate context or 2) lack a thoughtful consideration of both effectiveness and efficiency. Motivated by this, we propose \hyttInteractor, a BERT-based semantic matching model with a flexible contextualized interaction paradigm. It is capable of capturing fine-grained phrase-level information in the interaction, and thus is more effective to be applied for semantic matching tasks. Moreover, we further facilitate \hyttInteractor with a novel partial attention scheme, which significantly reduces the computational cost while maintaining the high effectiveness. We conduct comprehensive experimental evaluations on three datasets. The results show that \hyttInteractor achieves superior effectiveness and efficiency for semantic matching.
Assessing Algorithmic Biases for Musical Version Identification
Authors: Furkan Yesiler, Marius Miron, Joan Serrà, Emilia Gómez
Venue: WSDM
Year: 2022

Version identification (VI) systems now offer accurate and scalable solutions for detecting different renditions of a musical composition, allowing the use of these systems in industrial applications and throughout the wider music ecosystem. Such use can have an important impact on various stakeholders regarding recognition and financial benefits, including how royalties are circulated for digital rights management. In this work, we take a step toward acknowledging this impact and consider VI systems as socio-technical systems rather than isolated technologies. We propose a framework for quantifying performance disparities across 5 systems and 6 relevant side attributes: gender, popularity, country, language, year, and prevalence. We also consider 3 main stakeholders for this particular information retrieval use case: the performing artists of query tracks, those of reference (original) tracks, and the composers. By categorizing the recordings in our dataset using such attributes and stakeholders, we analyze whether the considered VI systems show any implicit biases. We find signs of disparities in identification performance for most of the groups we include in our analyses. We also find that learning- and rule-based systems behave differently for some attributes, which suggests an additional dimension to consider along with accuracy and scalability when evaluating VI systems. Lastly, we share our dataset to encourage VI researchers to take these aspects into account while building new systems.
Directed Network Embedding with Virtual Negative Edges
Authors: Hyunsik Yoo, Yeon-Chang Lee, Kijung Shin, Sang-Wook Kim
Venue: WSDM
Year: 2022

The directed network embedding problem is to represent the nodes in a given directed network as embeddings (i.e., low-dimensional vectors) that preserve the asymmetric relationships between nodes. While a number of approaches have been developed for this problem, we point out that existing approaches commonly face difficulties in accurately preserving asymmetric proximities between nodes in a sparse network containing a large number of low out- and in-degree nodes. In this paper, we focus on addressing this intrinsic difficulty caused by the lack of information. We first introduce the concept of virtual negative edges (VNEs), which represent latent negative relationships between nodes. Based on the concept, we propose a novel DIrected NE approach with VIrtual Negative Edges, named as DIVINE. DIVINE carefully decides the number and locations of VNEs to be added to the input network. Once VNEs are added, DIVINE learns embeddings by exploiting both the signs and directions of edges. Our experiments on four real-world directed networks demonstrate that adding VNEs alleviates the lack of information about low-degree nodes, thereby enabling DIVINE to yield high-quality embeddings that accurately capture asymmetric proximities between nodes. Specifically, the embeddings obtained by DIVINE lead to up to 10.16% more accurate link prediction, compared to those obtained by state-of-the-art competitors.
Bringing Your Own View: Graph Contrastive Learning without Prefabricated Data Augmentations
Authors: Yuning You, Tianlong Chen, Zhangyang Wang, Yang Shen
Venue: WSDM
Year: 2022

Self-supervision is recently surging at its new frontier of graph learning. It facilitates graph representations beneficial to downstream tasks; but its success could hinge on domain knowledge for handcraft or the often expensive trials and errors. Even its state-of-the-art representative, graph contrastive learning (GraphCL), is not completely free of those needs as GraphCL uses a prefabricated prior reflected by the ad-hoc manual selection of graph data augmentations. Our work aims at advancing GraphCL by answering the following questions: How to represent the space of graph augmented views? What principle can be relied upon to learn a prior in that space? And what framework can be constructed to learn the prior in tandem with contrastive learning? Accordingly, we have extended the prefabricated discrete prior in the augmentation set, to a learnable continuous prior in the parameter space of graph generators, assuming that graph priors per se, similar to the concept of image manifolds, can be learned by data generation. Furthermore, to form contrastive views without collapsing to trivial solutions due to the prior learnability, we have leveraged both principles of information minimization (InfoMin) and information bottleneck (InfoBN) to regularize the learned priors. Eventually, contrastive learning, InfoMin, and InfoBN are incorporated organically into one framework of bi-level optimization. Our principled and automated approach has proven to be competitive against the state-of-the-art graph self-supervision methods, including GraphCL, on benchmarks of small graphs; and shown even better generalizability on large-scale graphs, without resorting to human expertise or downstream validation. Our code is publicly released at https://github.com/Shen-Lab/GraphCL_Automated.
PrivacyCheck v3: Empowering Users with Higher-Level Understanding of Privacy Policies
Authors: Razieh Nokhbeh Zaeem, Ahmad Ahbab, Josh Bestor, Hussam H. Djadi, Sunny Kharel, Victor Lai, Nick Wang, K. Suzanne Barber
Venue: WSDM
Year: 2022

Online privacy policies are lengthy and hard to read, yet are profoundly important as they communicate the practices of an organization pertaining to user data privacy. Privacy Enhancing Technologies, or PETs, seek to inform users by summarizing these privacy policies. Efforts in the research and development of such PETs, however, have largely been limited to tools that recap the policy or visualize it. We present the next generation of our research and publicly available tool, PrivacyCheck v3, that utilizes machine learning to inform and empower users with respect to privacy policies. PrivacyCheck v3 adds capabilities that are commonly absent from similar PETs on the web. In particular, it adds the ability to (1) find the competitors of an organization with Alexa traffic analysis and compare policies across them, (2) follow privacy policies to which the user has agreed and notify the user when policies change, (3) track policies over time and report how often policies change and their trends, (4) automatically find privacy policies in domains, and (5) provide a bird's-eye view of privacy policies. The new features of PrivacyCheck not only inform users about details of privacy policies, but also empower them to understand privacy policies at a higher level, make informed decisions, and even select competitors with better privacy policies.
Learning Discrete Representations via Constrained Clustering for Effective and Efficient Dense Retrieval
Authors: Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Jiafeng Guo, Min Zhang, Shaoping Ma
Venue: WSDM
Year: 2022

Dense Retrieval (DR) has achieved state-of-the-art first-stage ranking effectiveness. However, the efficiency of most existing DR models is limited by the large memory cost of storing dense vectors and the time-consuming nearest neighbor search (NNS) in vector space. Therefore, we present RepCONC, a novel retrieval model that learns discrete Representations via CONstrained Clustering. RepCONC jointly trains dual-encoders and the Product Quantization (PQ) method to learn discrete document representations and enables fast approximate NNS with compact indexes. It models quantization as a constrained clustering process, which requires the document embeddings to be uniformly clustered around the quantization centroids and supports end-to-end optimization of the quantization method and dual-encoders. We theoretically demonstrate the importance of the uniform clustering constraint in RepCONC and derive an efficient approximate solution for constrained clustering by reducing it to an instance of the optimal transport problem. Besides constrained clustering, RepCONC further adopts a vector-based inverted file system (IVF) to support highly efficient vector search on CPUs. Extensive experiments on two popular ad-hoc retrieval benchmarks show that RepCONC achieves better ranking effectiveness than competitive vector quantization baselines under different compression ratio settings. It also substantially outperforms a wide range of existing retrieval models in terms of retrieval effectiveness, memory efficiency, and time efficiency.
Geometric Inductive Matrix Completion: A Hyperbolic Approach with Unified Message Passing
Authors: Chengkun Zhang, Hongxu Chen, Sixiao Zhang, Guandong Xu, Junbin Gao
Venue: WSDM
Year: 2022

Collaborative filtering is a central task in a broad range of recommender systems. As traditional methods train latent variables for user/item individuals under a transductive setting, it requires re-training for out-of-sample inferences. Inductive matrix completion (IMC) solves this problem by learning transformation functions upon engineered features, but it sacrifices model expressiveness and highly depends on feature qualities. In this paper, we propose Geometric Inductive Matrix Completion (GIMC) by introducing hyperbolic geometry and a unified message passing scheme into this generic task. The proposed method is the earliest attempt utilizing capacious hyperbolic space to enhance the capacity of IMC. It is the first work defining continuous explicit feedback prediction within non-Euclidean space by introducing hyperbolic regression for vertex interactions. This is also the first to provide comprehensive evidence that edge semantics can significantly improve recommendations, which is ignored by previous works. The proposed method outperforms the state-of-the-art algorithms with less than 1% parameters compared to its transductive counterparts. Extensive analysis and ablation studies are conducted to reveal the design considerations and practicability for a positive impact to the research community.
Leaving No One Behind: A Multi-Scenario Multi-Task Meta Learning Approach for Advertiser Modeling
Authors: Qianqian Zhang, Xinru Liao, Quan Liu, Jian Xu, Bo Zheng
Venue: WSDM
Year: 2022

Advertisers play an essential role in many e-commerce platforms like Taobao and Amazon. Fulfilling their marketing needs and supporting their business growth is critical to the long-term prosperity of platform economies. However, compared with extensive studies on user modeling such as click-through rate predictions, much less attention has been drawn to advertisers, especially in terms of understanding their diverse demands and performance. Different from user modeling, advertiser modeling generally involves many kinds of tasks (e.g. predictions of advertisers' expenditure, active-rate, or total impressions of promoted products). In addition, major e-commerce platforms often provide multiple marketing scenarios (e.g. Sponsored Search, Display Ads, Live Streaming Ads) while advertisers' behavior tend to be dispersed among many of them. This raises the necessity of multi-task and multi-scenario consideration in comprehensive advertiser modeling, which faces the following challenges: First, one model per scenario or per task simply doesn't scale; Second, it is particularly hard to model new or minor scenarios with limited data samples; Third, inter-scenario correlations are complicated, and may vary given different tasks. To tackle these challenges, we propose a multi-scenario multi-task meta learning approach (M2M) which simultaneously predicts multiple tasks in multiple advertising scenarios. Specifically, we introduce a novel meta unit that incorporates rich scenario knowledge to learn explicit inter-scenario correlations and can easily scale to new scenarios. Furthermore, we present a meta attention module to capture diverse inter-scenario correlations given different tasks, and a meta tower module to enhance the capability of capturing the representation of scenario-specific features. Compelling results from both offline evaluation and online A/B tests demonstrate the superiority of M2M over state-of-the-art methods.
Learning Concept Prerequisite Relations from Educational Data via Multi-Head Attention Variational Graph Auto-Encoders
Authors: Juntao Zhang, Nanzhou Lin, Xuelong Zhang, Wei Song, Xiandi Yang, Zhiyong Peng
Venue: WSDM
Year: 2022

Recently, the topic of learning concept prerequisite relations has gained the attention of many researchers, which is crucial in the learning process for a learner to decide an optimal study order. However, the existing work still ignores three key factors. (1) People's cognitive differences could make a difference for annotating the prerequisite relation between resources (e.g., courses, textbooks) or concepts (e.g., binary tree). (2) The current vertex (resources or concepts) can be affected by the feature of the neighbor vertex in the resource or concept graph. (3) The feature information of the resource graph may affect the concept graph. To integrate the above factors, we propose an end-to-end graph network-based model called Multi-Head Attention Variational Graph Auto-Encoders (MHAVGAE ) to learn the prerequisite relation between concepts via a resource-concept graph. To address the first two problems, we introduce the multi-head attention mechanism to operate and compute the hidden representations of each vertex over the resource-concept graph. Then, we design a gated fusion mechanism to integrate the feature information of the resource and concept graphs to enrich concept content features. Finally, we conduct numerous experiments to demonstrate the effectiveness of the MHAVGAE across multiple widely used metrics compared with the state-of-the-art methods. The experimental results show that the performance of the MHAVGAE almost outperforms all the baseline methods.
A GNN-based Multi-task Learning Framework for Personalized Video Search
Authors: Li Zhang, Lei Shi, Jiashu Zhao, Juan Yang, Tianshu Lyu, Dawei Yin, Haiping Lu
Venue: WSDM
Year: 2022

Watching online videos has become more and more popular and users tend to watch videos based on their personal tastes and preferences. Providing a customized ranking list to maximize the user's satisfaction has become increasingly important for online video platforms. Existing personalized search methods (PSMs) train their models with user feedback information (e.g. clicks). However, we identified that such feedback signals may indicate attractiveness but not necessarily indicate relevance in video search. Besides, the click data and user historical information are usually too sparse to train a good PSM, which is different from the conventional Web search containing users' rich historical information. To address these concerns, in this paper we propose a multi-task graph neural network architecture for personalized video search (MGNN-PVS) that can jointly model user's click behaviour and the relevance between queries and videos. To relieve the sparsity problem and learn better representation for users, queries and videos, we develop an efficient and novel GNN architecture based on neighborhood sampling and hierarchical aggregation strategy by leveraging their different hops of neighbors in the user-query and query-document click graph. Extensive experiments on a major commercial video search engine show that our model significantly outperforms state-of-the-art PSMs, which illustrates the effectiveness of our proposed framework.
GraSP: Optimizing Graph-based Nearest Neighbor Search with Subgraph Sampling and Pruning
Authors: Minjia Zhang, Wenhan Wang, Yuxiong He
Venue: WSDM
Year: 2022

Nearest Neighbor Search (NNS) has recently drawn a rapid growth of interest because of its core role in high-dimensional vector data management in data science and AI applications. The interest is fueled by the success of neural embedding, where deep learning models transform unstructured data into semantically correlated feature vectors for data analysis, e.g., recommending popular items. Among several categories of methods for fast NNS, graph-based approximate nearest neighbor search algorithms have led to the best-in-class search performance on a wide range of real-world datasets. While prior works improve graph-based NNS search efficiency mainly through exploiting the structure of the graph with sophisticated heuristic rules, in this work, we show that the frequency distributions of edge visits for graph-based NNS can be highly skewed. This finding leads to the study of pruning unnecessary edges to avoid redundant computation during graph traversal by utilizing the query distribution, an important yet under-explored aspect of graph-based NNS. In particular, we formulate graph pruning as a discrete optimization problem, and introduce a graph optimization algorithm GraSP that improves the search efficiency of similarity graphs by learning to prune redundant edges. GraSP enhances an existing similarity graph with a probabilistic model. It then performs a novel subgraph sampling and iterative refinement optimization to explicitly maximize search efficiency when removing a subset of edges in expectation over a graph for a large set of training queries. The evaluation shows that GraSP consistently improves the search efficiency on real-world datasets, providing up to 2.24X faster search speed than state-of-the-art methods without losing accuracy.