Zhongyi Liu 0001

dblp:46/394-1 · DBLP profile ↗
← Back
20ranked-venue papers in the field
0as first author
17since 2021 · last 2024
0000-0001-9478-8107ORCID · conflict

Domains — venue-derived; a paper can count in several

Information Retrieval & Web Search · 10Database Systems & Data Management · 6Data Mining & Knowledge Discovery · 3Knowledge Engineering, Semantic Web & Information Systems · 1
YearPublicationVenuePosition
2024 Exploring Multi-Scenario Multi-Modal CTR Prediction with a Large Scale Dataset
abstract
Click-through rate (CTR) prediction plays a crucial role in recommendation systems, with significant impact on user experience and platform revenue generation. Despite the various public CTR datasets available due to increasing interest from both academia and industry, these datasets have limitations. They cover a limited range of scenarios and predominantly focus on ID-based features, neglecting the vital role of multi-modal features for effective multi-scenario CTR prediction. Moreover, their scale is modest compared to real-world industrial datasets, hindering robust and comprehensive evaluation of complex models. To address these challenges, we introduce a large-scale Multi-Scenario Multi-Modal CTR dataset named AntM2 C, built from real industrial data from Alipay. This dataset offers an impressive breadth and depth of information, covering CTR data from four diverse business scenarios, including advertisements, consumer coupons, mini-programs, and videos. Unlike existing datasets, AntM2 C provides not only ID-based features but also five textual features and one image feature for both users and items, supporting more delicate multi-modal CTR prediction. AntM2 C is also substantially larger than existing datasets, comprising 100 million CTR data. This scale allows for robust and comprehensive evaluation and comparison of CTR prediction models. We employ AntM2 C to construct several typical CTR tasks, including multi-scenario modeling, item and user cold-start modeling, and multi-modal modeling. Initial experiments and comparisons with baseline methods have shown that AntM2 C presents both new challenges and opportunities for CTR models, with the potential to significantly advance CTR research. The AntM2 C dataset is available at https://www.atecup.cn/OfficalDataSet.
Zhaoxin Huan, Ke Ding 0001, Ang Li 0043, Xu Min, Yong He 0009, Liang Zhang 0045, Jun Zhou 0011, Linjian Mo, Jinjie Gu, Zhongyi Liu 0001, Leon Wenliang Zhong, Chenliang Li 0005, Fajie Yuan
SIGIR11
2024 LLMGR: Large Language Model-based Generative Retrieval in Alipay Search
abstract
The search system aims to help users quickly find items according to queries they enter, which includes the retrieval and ranking modules. Traditional retrieval is a multi-stage process, including indexing and sorting, which cannot be optimized end-to-end. With the real data about mini-apps in the Alipay search, we find that many complex queries fail to display the relevant mini-apps, seriously threatening users' search experience. To address the challenges, we propose a Large Language Model-based Generative Retrieval (LLMGR) approach for retrieving mini-app candidates. The information of the mini-apps is encoded into the large model, and the title of the mini-app is directly generated. Through the online A/B test in Alipay search, LLMGR as a supplementary source has statistically significant improvements in the Click-Through Rate (CTR) of the search system compared to traditional methods. In this paper, we have deployed a novel retrieval method for the Alipay search system and demonstrated that generative retrieval methods based on LLM can improve the performance of search system, particularly for complex queries, which have an average increase of 0.2% in CTR.
Wei Chen 0158, Yixin Ji, Jia Xu 0013, Zhongyi Liu 0001
SIGIR5
2024 Multi-Intent Attribute-Aware Text Matching in Searching
abstract
Text matching systems have become a fundamental service in most Searching platforms. For instance, they are responsible for matching user queries to relevant candidate items, or rewriting the user-input query to a pre-selected high-performing one for a better search experience. In practice, both the queries and items often contain multiple attributes, such as the category of the item and the location mentioned in the query, which represent condensed key information that is helpful for matching. However, most of the existing works downplay the effectiveness of attributes by integrating them into text representations as supplementary information. Hence, in this work, we focus on exploring the relationship between the attributes from two sides. Since attributes from two ends are often not aligned in terms of number and type, we propose to exploit the benefit of attributes by multiple-intent modeling. The intents extracted from attributes summarize the diverse needs of queries and provide rich content of items, which are more refined and abstract, and can be aligned for paired inputs. Concretely, we propose a multi-intent attribute-aware matching model (MIM), which consists of three main components: attribute-aware encoder, multi-intent modeling, and intent-aware matching. In the attribute-aware encoder, the text and attributes are weighted and processed through a scaled attention mechanism with regard to the attributes' importance. Afterward, the multi-intent modeling extracts intents from two ends and aligns them. Herein, we come up with a distribution loss to ensure the learned intents are diverse but concentrated, and a kullback-leibler divergence loss that aligns the learned intents. Finally, in the intent-aware matching, the intents are evaluated by a self-supervised masking task, and then incorporated to output the final matching result. Extensive experiments on three real-world datasets from different matching scenarios show that MIM significantly outperforms state-of-the-art matching baselines. MIM is also tested by online A/B test, which brings significant improvements over three business metrics in query rewriting and query-item relevance tasks compared with the online baseline in Alipay App.
Mingzhe Li 0001, Xiuying Chen, Jing Xiang, Qishen Zhang, Changsheng Ma, Chenchen Dai, Jinxiong Chang, Zhongyi Liu 0001
WSDM8
2024 A Multi-Granularity-Aware Aspect Learning Model for Multi-Aspect Dense Retrieval
abstract
Dense retrieval methods have been mostly focused on unstructured text and less attention has been drawn to structured data with various aspects, e.g., products with aspects such as category and brand. Recent work has proposed two approaches to incorporate the aspect information into item representations for effective retrieval by predicting the values associated with the item aspects. Despite their efficacy, they treat the values as isolated classes (e.g., "Smart Homes", "Home, Garden & Tools", and "Beauty & Health") and ignore their fine-grained semantic relation. Furthermore, they either enforce the learning of aspects into the CLS token, which could confuse it from its designated use for representing the entire content semantics, or learn extra aspect embeddings only with the value prediction objective, which could be insufficient especially when there are no annotated values for an item aspect.
Xiaojie Sun 0003, Keping Bi, Jiafeng Guo, Sihui Yang, Qishen Zhang, Zhongyi Liu 0001, Xueqi Cheng 0001
WSDM6
2024 Towards Better Chinese Spelling Check for Search Engines: A New Dataset and Strong Baseline
abstract
Misspellings in search engine queries may prevent search engines from returning accurate results. For Chinese mobile search engines, due to the different input methods (e.g., hand-written and T9 input methods), more types of misspellings exist, making this problem more challenging. As an essential module of search engines, Chinese Spelling Check~(CSC) models aim to detect and correct misspelled Chinese characters from user-issued queries. Despite the great value of CSC to the search engine, there is no CSC benchmark collected from real-world search engine queries. To fill this blank, we construct and release the Alipay Search Engine Query (AlipaySEQ) spelling check dataset. To the best of our knowledge, AlipaySEQ is the first Chinese Spelling Check dataset collected from the real-world scenario of Chinese mobile search engines. It consists of 15,522 high-quality human annotated and 1,175,151 automatically generated samples. To demonstrate the unique challenges of AlipaySEQ in the era of Large Language Models~(LLMs), we conduct a thorough study to analyze the difference between AlipaySEQ and existing SIGHAN benchmarks and compare the performance of various baselines, including existing task-specific methods and LLMs. We observe that all baselines fail to perform satisfactorily due to the over-correction problem. Especially, LLMs exhibit below-par performance on AlipaySEQ, which is rather surprising. Therefore, to alleviate the over-correction problem, we introduce a model-agnostic CSC Self-Refine Framework (SRF) to construct a strong baseline. Comprehensive experiments demonstrate that our proposed SRF, though more effective against existing models on both the AlipaySEQ and SIGHAN15, is still far from achieving satisfactory performance on our real-world dataset. With the newly collected real-world dataset and strong baseline, we hope more progress can be achieved on such a challenging and valuable task.
Yue Wang 0039, Zilong Zheng, Zecheng Tang, Juntao Li 0005, Kunlong Chen, Jinxiong Chang, Qishen Zhang, Zhongyi Liu 0001, Min Zhang 0005
WSDM9
2024 Unify Graph Learning with Text: Unleashing LLM Potentials for Session Search
abstract
Session search involves a series of interactive queries and actions to fulfill user's complex information need. Current strategies typically prioritize sequential modeling for deep semantic understanding, overlooking the graph structure in interactions. While some approaches focus on capturing structural information, they use a generalized representation for documents, neglecting the word-level semantic modeling. In this paper, we propose Symbolic Graph Ranker (SGR), which aims to take advantage of both text-based and graph-based approaches by leveraging the power of recent Large Language Models (LLMs). Concretely, we first introduce a set of symbolic grammar rules to convert session graph into text. This allows integrating session history, interaction process, and task instruction seamlessly as inputs for the LLM. Moreover, given the natural discrepancy between LLMs pre-trained on textual corpora, and the symbolic language we produce using our graph-to-text grammar, our objective is to enhance LLMs' ability to capture graph structures within a textual format. To achieve this, we introduce a set of self-supervised symbolic learning tasks including link prediction, node content generation, and generative contrastive learning, to enable LLMs to capture the topological information from coarse-grained to fine-grained. Experiment results and comprehensive analysis on two benchmark datasets, AOL and Tiangong-ST, confirm the superiority of our approach. Our paradigm also offers a novel and effective methodology that bridges the gap between traditional search strategies and modern LLMs.
Songhao Wu, Quan Tu, Jia Xu 0013, Zhongyi Liu 0001, Xiuying Chen, Rui Yan 0001
WWW5
2024 Graphusion: Latent Diffusion for Graph Generation
abstract
Graph generation is a fundamental task in machine learning with broad impacts on numerous real-world applications such as biomedical discovery and social science. Most recently, generative models, especially diffusion models (DMs), have shown great promise in synthesizing realistic graphs. However, existing DMs methods typically conduct diffusion processes directly in complex graph space (i.e., node feature, adjacency matrix, or both), resulting in high modeling complexity and poor multimodal distribution coverage. In this paper, we propose Graphusion, a novel and unified latent-based graph generative framework to address the problems. Specifically, Graphusion is composed of a variational graph autoencoder mapping raw graphs with high-dimensional discrete space to low-dimensional topology-injected latent space, and latent DMs running there, producing a smoother, faster, and more expressive graph generation procedure. Thanks to the latest space modeling, we further develop principled latent self-guidance to sufficiently cover the whole semantical distribution of the unlabeled graph set. Experiments show that our Graphusion framework can consistently outperform previous graph generation baselines on both generic and molecular graph datasets, demonstrating the generality and extensibility along with further analytical justifications.
Ling Yang 0006, Zhilin Huang, Zhongyi Liu 0001, Shenda Hong, Wentao Zhang 0001, Wenming Yang, Bin Cui 0001, Luxia Zhang
IEEE Trans. Knowl. Data Eng.4
2024 Individual and Structural Graph Information Bottlenecks for Out-of-Distribution Generalization
abstract
Out-of-distribution (OOD) graph generalization are critical for many real-world applications. Existing methods neglect to discard spurious or noisy features of inputs, which are irrelevant to the label. Besides, they mainly conduct instance-level class-invariant graph learning and fail to utilize the structural class relationships between graph instances. In this work, we endeavor to address these issues in a unified framework, dubbedIndividual andStructuralGraphInformationBottlenecks (IS-GIB). To remove class spurious feature caused by distribution shifts, we propose Individual Graph Information Bottleneck (I-GIB) which discards irrelevant information by minimizing the mutual information between the input graph and its embeddings. To leverage the structural intra- and inter-domain correlations, we propose Structural Graph Information Bottleneck (S-GIB). Specifically for a batch of graphs with multiple domains, S-GIB first computes the pair-wise input-input, embedding-embedding, and label-label correlations. Then it minimizes the mutual information between input graph and embedding pairs while maximizing the mutual information between embedding and label pairs. The critical insight of S-GIB is to simultaneously discard spurious features and learn invariant features from a high-order perspective by maintaining class relationships under multiple distributional shifts. Notably, we unify the proposed I-GIB and S-GIB to form our complementary framework IS-GIB. Extensive experiments conducted on both node- and graph-level tasks consistently demonstrate the superior generalization ability of IS-GIB. The code is available athttps://github.com/YangLing0818/GraphOOD.
Ling Yang 0006, Heyuan Wang 0001, Zhongyi Liu 0001, Zhilin Huang, Shenda Hong, Wentao Zhang 0001, Bin Cui 0001
IEEE Trans. Knowl. Data Eng.4
2023 Beyond Semantics: Learning a Behavior Augmented Relevance Model with Self-supervised Learning
abstract
Relevance modeling aims to locate desirable items for corresponding queries, which is crucial for search engines to ensure user experience. Although most conventional approaches address this problem by assessing the semantic similarity between the query and item, pure semantic matching is not everything. In reality, auxiliary query-item interactions extracted from user historical behavior data of the search log could provide hints to reveal users' search intents further. Drawing inspiration from this, we devise a novel Behavior Augmented Relevance Learning model for Alipay Search (BARL-ASe) that leverages neighbor queries of target item and neighbor items of target query to complement target query-item semantic matching. Specifically, our model builds multi-level co-attention for distilling coarse-grained and fine-grained semantic representations from both neighbor and target views. The model subsequently employs neighbor-target self-supervised learning to improve the accuracy and robustness of BARL-ASe by strengthening representation and logit learning. Furthermore, we discuss how to deal with the long-tail query-item matching of the mini apps search scenario of Alipay practically. Experiments on real-world industry data and online A/B testing demonstrate our proposal achieves promising performance with low latency.
Wei Chen 0158, Jia Xu 0013, Zhongyi Liu 0001, Wei Zhang 0056
CIKM4
2023 An Unified Search and Recommendation Foundation Model for Cold-Start Scenario
abstract
In modern commercial search engines and recommendation systems, data from multiple domains is available to jointly train the multi-domain model. Traditional methods train multi-domain models in the multi-task setting, with shared parameters to learn the similarity of multiple tasks, and task-specific parameters to learn the divergence of features, labels, and sample distributions of individual tasks. With the development of large language models, LLM can extract global domain-invariant text features that serve both search and recommendation tasks. We propose a novel framework called S&R Multi-Domain Foundation, which uses LLM to extract domain invariant features, and Aspect Gating Fusion to merge the ID feature, domain invariant text features and task-specific heterogeneous sparse features to obtain the representations of query and item. Additionally, samples from multiple search and recommendation scenarios are trained jointly with Domain Adaptive Multi-Task module to obtain the multi-domain foundation model. We apply the S&R Multi-Domain foundation model to cold start scenarios in the pretrain-finetune manner, which achieves better performance than other SOTA transfer learning methods. The S&R Multi-Domain Foundation model has been successfully deployed in Alipay Mobile Application's online services, such as content query recommendation and service card recommendation, etc.
Yuqi Gong, Xichen Ding, Yehui Su, Kaiming Shen, Zhongyi Liu 0001
CIKM5
2023 Pre-training with Aspect-Content Text Mutual Prediction for Multi-Aspect Dense Retrieval
abstract
Grounded on pre-trained language models (PLMs), dense retrieval has been studied extensively on plain text. In contrast, there has been little research on retrieving data with multiple aspects using dense models. In the scenarios such as product search, the aspect information plays an essential role in relevance matching, e.g., category: Electronics, Computers, and Pet Supplies. A common way of leveraging aspect information for multi-aspect retrieval is to introduce an auxiliary classification objective, i.e., using item contents to predict the annotated value IDs of item aspects. However, by learning the value embeddings from scratch, this approach may not capture the various semantic similarities between the values sufficiently. To address this limitation, we leverage the aspect information as text strings rather than class IDs during pre-training so that their semantic similarities can be naturally captured in the PLMs. To facilitate effective retrieval with the aspect strings, we propose mutual prediction objectives between the text of the item aspect and content. In this way, our model makes more sufficient use of aspect information than conducting undifferentiated masked language modeling (MLM) on the concatenated text of aspects and content. Extensive experiments on two real-world datasets (product and mini-program search) show that our approach can outperform competitive baselines both treating aspect values as classes and conducting the same MLM for aspect and content strings. Code and related dataset will be available at the URL \footnotehttps://github.com/sunxiaojie99/ATTEMPT.
Xiaojie Sun 0003, Keping Bi, Jiafeng Guo, Xinyu Ma 0001, Yixing Fan, Hongyu Shan, Qishen Zhang, Zhongyi Liu 0001
CIKM8
2023 Disentangled Interest importance aware Knowledge Graph Neural Network for Fund Recommendation
abstract
At present, people are gradually becoming aware of financial management and thus fund recommendation attracts more and more attention to help them find suitable funds quickly. As a user usually takes many factors (e.g., fund theme, fund manager) into account when investing a fund and the fund usually consists of a substantial collection of investments, effectively modeling multi-interest representations is more crucial for personalized fund recommendation than the traditional goods recommendation. However, existing multi-interest methods are largely sub-optimal for fund recommendation, since they ignore financial domain knowledge and diverse fund investment intentions. In this work, we propose a Disentangled Interest importance aware Knowledge Graph Neural Network (DIKGNN) for personalized fund recommendation on FinTech platforms. In particular, we restrict the multiple intent spaces by introducing the attribute nodes from the fund knowledge graph as the minimum intent modeling unit to utilize financial domain knowledge and provide interpretability. In the intent space, we define disentangled intent representations, equipped with intent importance distributions to describe the diverse fund investment intentions. Then we design a new neighbor aggregation mechanism with the learned intent importance distribution upon the interaction graph and knowledge graph to collect multi-intent information. Furthermore, we leverage micro independence and macro balance constraints on the representations and distributions respectively to encourage intent independence and diversity. The extensive experiments on public recommendation benchmarks demonstrate that DIKGNN can achieve substantial improvement over state-of-the-art methods. Our proposed model is also evaluated over one real-world industrial fund dataset from a FinTech platform and has been deployed online.
Ke Tu, Zhengwei Wu, Zhiqiang Zhang 0012, Zhongyi Liu 0001, Le Wu 0001, Jun Zhou 0011
CIKM5
2023 GARCIA: Powering Representations of Long-tail Query with Multi-granularity Contrastive Learning
abstract
Recently, the growth of service platforms brings great convenience to both users and merchants, where the service search engine plays a vital role in improving the user experience by quickly obtaining desirable results via textual queries. Unfortunately, users’ uncontrollable search customs usually bring vast amounts of long-tail queries, which severely threaten the capability of search models. Inspired by recently emerging graph neural networks (GNNs) and contrastive learning (CL), several efforts have been made in alleviating the long-tail issue and achieve considerable performance. Nevertheless, they still face a few major weaknesses. Most importantly, they do not explicitly utilize the contextual structure between heads and tails for effective knowledge transfer, and intention-level information is commonly ignored for more generalized representations.To this end, we develop a novel framework GARCIA, which exploits the graph based knowledge transfer and intention based representation generalization in a contrastive setting. In particular, we employ an adaptive encoder to produce informative representations for queries and services, as well as hierarchical structure aware representations of intentions. To fully understand tail queries and services, we equip GARCIA with a novel multi-granularity contrastive learning module, which powers representations through knowledge transfer, structure enhancement and intention generalization. Subsequently, the complete GARCIA is well trained in a pre-training&fine-tuning manner. At last, we conduct extensive experiments on both offline and online environments, which demonstrates the superior capability of GARCIA in improving tail queries and overall performance in service search scenarios.
Weifan Wang 0005, Binbin Hu, Zhicheng Peng, Mingjie Zhong, Zhiqiang Zhang 0012, Zhongyi Liu 0001, Jun Zhou 0011
ICDE6
2023 Beyond Two-Tower: Attribute Guided Representation Learning for Candidate Retrieval
abstract
Candidate retrieval is a key part of the modern search engines whose goal is to find candidate items that are semantically related to the query from a large item pool. The core difference against the later ranking stage is the requirement of low latency. Hence, two-tower structure with two parallel yet independent encoder for both query and item is prevalent in many systems. In these efforts, the semantic information of a query and a candidate item is fed into the corresponding encoder and then use their representations for retrieval. With the popularity of pre-trained semantic models, the state-of-the-art for semantic retrieval tasks has achieved the significant performance gain.
Hongyu Shan, Qishen Zhang, Zhongyi Liu 0001, Chenliang Li 0005
WWW3
2023 Learning Dynamic User Interest Sequence in Knowledge Graphs for Click-Through Rate Prediction
abstract
Despite that path-based and embedding-based models with knowledge graphs (KGs) achieve better recommendation performance compared with other deep learning based methods, such improvement is limited due to a lack of modeling user's dynamic interest. To address this issue, we explore a principled model to provide semantic understanding of each item in user's historical interest sequence in KGs. Specifically, we propose a multi-granularity dynamic interest sequence learning method, which is based on knowledge-enhanced path mining and interest fluctuation signal discovery, to obtain semantic-enhanced paths. Furthermore, the paths are embedded by the SEP2Vec, and merged through the proposed entropy-aware pooling layer to obtain the user preference representation, which is then used to learn dynamic user interest sequence. Experimental results on two public datasets of movie and music recommendation, and two industrial datasets of personalized local service recommendation in Alipay App have illustrated that the proposed model can achieve significantly better prediction performance compared with other known baselines.
Youru Li, Wenfang Lin, Mingjie Zhong, Qunwei Li, Zhongyi Liu 0001, Leon Wenliang Zhong, Zhenfeng Zhu
IEEE Trans. Knowl. Data Eng.6
2022 Cross-Domain Product Search with Knowledge Graph
abstract
The notion personalization lies on the core of a real-world product search system, whose aim is to understand the user's search intent in a fine-grained level. The existing solutions mainly achieve this purpose through a coarse-grained semantic matching in terms of the query and item's description or the collective click correlations. Besides the issued query, the historical search behaviors of a user would cover lots of her personalized interests, which is a promising avenue to alleviate the semantic gap between users, items and queries. However, as to a specific domain, a user's search behaviors are generally sparse or even unavailable (i.e., cold-start users). How to exploit the search behaviors from the other relevant domain and enable effective fine-grained intent understanding remains largely unexplored for product search. Moreover, the semantic gap could be further aggravated since the properties of an item could evolve over time (e.g., the price adjustment for a mobile phone or the business plan update for a financial item), which is also mainly overlooked by the existing solutions.
Zhongyi Liu 0001, Chenliang Li 0005
CIKM4
2022 Automatic Expert Selection for Multi-Scenario and Multi-Task Search
abstract
Multi-scenario learning (MSL) enables a service provider to cater for users' fine-grained demands by separating services for different user sectors, e.g., by user's geographical region. Under each scenario there is a need to optimize multiple task-specific targets e.g., click through rate and conversion rate, known as multi-task learning (MTL). Recent solutions for MSL and MTL are mostly based on the multi-gate mixture-of-experts (MMoE) architecture. MMoE structure is typically static and its design requires domain-specific knowledge, making it less effective in handling both MSL and MTL. In this paper, we propose a novel Automatic Expert Selection framework for Multi-scenario and Multi-task search, named AESM2. AESM2 integrates both MSL and MTL into a unified framework with an automatic structure learning. Specifically, AESM2 stacks multi-task layers over multi-scenario layers. This hierarchical design enables us to flexibly establish intrinsic connections between different scenarios, and at the same time also supports high-level feature extraction for different tasks. At each multi-scenario/multi-task layer, a novel expert selection algorithm is proposed to automatically identify scenario-/task-specific and shared experts for each input. Experiments over two real-world large-scale datasets demonstrate the effectiveness of AESM2 over a battery of strong baselines. Online A/B test also shows substantial performance gain on multiple metrics. Currently, AESM2 has been deployed online for serving major traffic.
Xuchu Ding, Zhongyi Liu 0001, Chenliang Li 0005, Aixin Sun
SIGIR5
2020 DKEN: Deep knowledge-enhanced network for recommender systems
Wenfang Lin, Youru Li, Zhongyi Liu 0001, Zhenfeng Zhu
Inf. Sci.4
2018 Fast Parallel Path Concatenation for Graph Extraction
abstract
In this paper, we study the problem of extracting a homogeneous graph from a heterogeneous graph. The key challenges of the extraction problem are how to efficiently enumerate paths matched by the provided line pattern and aggregate values for each pair of vertices from the matched paths. To address above two challenges, we propose a parallel graph extraction framework (PGE), where we use vertex-centric model to enumerate paths and compute aggregate functions in parallel. The framework compiles the line pattern into a path concatenation plan and generates the final weighted edges in a divide-and-conquer manner. The new solution outperforms the state-of-the-art ones through the comprehensive experiments.
Yingxia Shao, Kai Lei, Lei Chen 0002, Zi Huang, Bin Cui 0001, Zhongyi Liu 0001, Yunhai Tong, Jin Xu 0002
ICDE6
2017 Fast Parallel Path Concatenation for Graph Extraction
abstract
Heterogeneous graph is a popular data model to represent the real-world relations with abundant semantics. To analyze heterogeneous graphs, an important step is extracting homogeneous graphs from the heterogeneous graphs, called homogeneous graph extraction. In an extracted homogeneous graph, the relation is defined by a line pattern on the heterogeneous graph and the new attribute values of the relation are calculated by user-defined aggregate functions. The key challenges of the extraction problem are how to efficiently enumerate paths matched by the line pattern and aggregate values for each pair of vertices from the matched paths. To address above two challenges, we propose a parallel graph extraction framework, where we use vertex-centric model to enumerate paths and compute aggregate functions in parallel. The framework compiles the line pattern into a path concatenation plan, which determines the order of concatenating paths and generates the final paths in a divide-and-conquer manner. We introduce a cost model to estimate the cost of a plan and discuss three plan selection strategies, among which the best plan can enumerate paths in O(log)(l) iterations, where l is the length of a pattern. Furthermore, to improve the performance of evaluating aggregate functions, we classify the aggregate functions into three categories, i.e., distributive aggregation, algebraic aggregation, and holistic aggregation. Since the distributive and algebraic aggregations can be computed from the partial paths, we speed up the aggregation by computing partial aggregate values during the path enumeration.
Yingxia Shao, Kai Lei, Lei Chen 0002, Zi Huang, Bin Cui 0001, Zhongyi Liu 0001, Yunhai Tong, Jin Xu 0002
IEEE Trans. Knowl. Data Eng.6