The blossoming of large language models (LLMs) has greatly shifted the paradigm of Sequential Recommender System (SRS). Numerous studies have attempted to integrate ID-based collaborative signals and text information for effectively capturing both ID semantics and text semantics to enhance LLM-based recommendation. However, existing fusion methods suffer from challenges like fusion noise and the semantic gap. To address these issues, we propose Hybrid Dual-Semantics Modeling for enhancing LLM-based Recommendation (HDRec), an effective hybrid fusion method based on a design of dual low-rank adaptation (LoRA). HDRec employs two LoRAs processes on a shared LLM decoder, with each process handling information from one of the two semantics. We further implement a dedicated fusion mechanism exclusively at the inference stage, allowing the robust textual representation to serve as the primary signal, which is adaptively enhanced by unique collaborative signals from ID semantics, ensuring stable and accurate final predictions. To mitigate gradient conflicts caused by the dual LoRA processes, we introduce the alternating training of dual low-rank adaptation strategy. This method effectively resolves gradient conflicts and enables successful optimization of HDRec. Extensive experiments show that HDRec outperforms existing non-LLM-based and LLM-based state-of-the-art methods. The implementation of HDRec is anonymously available at https://github.com/KDEGroup/HDRec.

Visually-aware recommender system (VARS) has become increasingly prevalent in various online services by integrating visual features of items to enhance recommendation quality. However, VARS introduces new security vulnerabilities and malicious attackers can perform visual shilling attacks to manipulate recommendation lists via uploading generated images with visually imperceptible perturbations. While prior research has explored such threats to help service providers enhance their systems, existing visual shilling attack methods still suffer from uncontrolled pixel-space perturbation, energy dispersion dilemma and semantic misalignment in reference selection. In this work, we present Semantic-Constrained Diffusion Adversarial Generation (SC-DAG) for visual shilling attacks. SC-DAG overcomes key limitations of previous methods by focusing perturbations on semantically meaningful image regions through contour-aware segmentation, guiding adversarial generation in latent space using a conditional diffusion process, and performing a hybrid reference image selection strategy that balances popularity and semantic similarity. Extensive experiments on performing visual shilling attacks against multiple VARS models show that SC-DAG achieves state-of-the-art attack performance in elevating target items' ranking, while maintaining strong perceptual indistinguishability and minimal impact on overall recommendation performance of the system. Our work offers insights into leveraging structured semantic priors for more sophisticated adversarial manipulations against VARS and also highlights the necessity for developing more robust VARS models resilient to visual shilling attacks. We provide our implementation at https://github.com/KDEGroup/SC-DAG.

Subgraph matching (SM) is a fundamental problem in graph data analysis. Real-world patterns used in graph analysis are often symmetric and contain isomorphic substructures, but existing SM algorithms fail to explore such properties. To fill this gap, we propose MuSha, a multi-objective optimization framework for SM, leveraging multilevel sharing of isomorphic substructure results to speed up SM and symmetry breaking to avoid directly computing symmetric results. To efficiently compute and cache intermediate results for sharing, MuSha applies worst-case optimal joins (WCOJs) and utilizes trie data structures to compress and index results. To enable multilevel sharing, MuSha solves a multi-objective optimization problem involving pattern decomposition, symmetry breaking, WCOJ orders, and trie structural orders. Experimental results demonstrate that MuSha outperforms the state of the art by up to two orders of magnitude on graphs of millions of vertices.

Road network applications, such as navigation, incident detection, and Point-of-Interest (POI) recommendation, make extensive use of network edge weights (e.g., traveling times). Some of these weights can be missing, especially in a road network where traffic data may not be available for every road. In this article, we study the stochastic weight completion (SWC) problem, which computes the weight distributions of missing road edges. This is difficult, due to the intricate temporal and spatial correlations among neighboring edges. Besides, the road network can be sparse , i.e., there is a lack of traveling information in a large portion of the network. To tackle these challenges, we propose a multi-granularity framework for Region-Wise Graph Completion (RegGC) . To learn coarse spatial correlations among distantly located roads, we construct a region-wise hypergraph neural architecture based on semantic region dependencies. For finer spatial correlations, we incorporate contextual road network properties (e.g., speed limits, lane counts, and road types). Moreover, it incorporates recent and periodic dimensions of road traffic. We evaluate RegGC against 10 existing methods on 3 real road network datasets. They show that RegGC is more effective and efficient than state-of-the-art solutions.

The subgraph matching problem is crucial in graph analysis, involving identifying all instances of a given pattern$P$within a graph$G$. Advances in this field aim to uncover larger patterns across diverse graph types and subgraph matching tasks. However, existing methods often prove inefficient for such tasks. To address this gap, we propose CSCE, which generates efficient plans for various problem settings. CSCE utilizes clustered compressed sparse rows for heterogeneous graphs and sequential candidate equivalence to reduce redundant computations. Moreover, our approach seamlessly supports different subgraph matching variants, such as edge-induced, vertex-induced, and homomorphic scenarios. Experiments show that our work is up to two orders of magnitude faster than the state of the art on graphs of millions scale.

While motif has been widely employed in graph analytics, a fundamental question remains open: How should overlapping motif edges connect into a path? Existing works address this question with simple but inconsistent generalizations from standard graphs. This paper studies this issue by proposing the concept of connectivity degree (CD), i.e. the number of overlapping nodes needed for motif edges to be adjacent, as the requirement for path connection. We further study three research questions. First, is CD significant? We study how CD impacts motif analytics, more specifically, three motif-based methods. Second, how to estimate the right CD? We develop a minimax estimator based on minimizing the worst-case risk. Finally, how to detect the connected components with connectivity degree, an important task by itself and necessary for our estimator. As the traditional BFS or DFS approaches are not valid anymore, we develop a disjoint set algorithm instead. Our experiments validate that our CD can improve the performance of motif analytics. Also, our estimator is effective and our connected component detection algorithm is efficient.

Entity alignment (EA), a crucial task in knowledge graph (KG) research, aims to identify equivalent entities across different KGs to support downstream tasks like KG integration, text-to-SQL, and question-answering systems. Given rich semantic information within KGs, pre-trained language models (PLMs) have shown promise in EA tasks due to their exceptional context-aware encoding capabilities. However, the current solutions based on PLMs encounter obstacles such as the need for extensive training, expensive data annotation, and inadequate incorporation of structural information. In this study, we introduce a novel zero-training EA framework, ZeroEA, which effectively captures both semantic and structural information for PLMs. To be specific, Graph2Prompt module serves as the bridge between graph structure and plain text by converting KG topology into textual context suitable for PLM input. Additionally, in order to provide PLMs with concise and clear input text of reasonable length, we design a motif-based neighborhood filter to eliminate noisy neighbors. The comprehensive experiments and analyses on 5 benchmark datasets demonstrate the effectiveness of ZeroEA, outperforming all leading competitors and achieving state-of-the-art performance in entity alignment. Notably, our study highlights the considerable potential of EA technique in improving the performance of downstream tasks, thereby benefitting the broader research field.

Given a graph G , a motif (e.g., 3-node clique) is a fundamental building block for G. Recently, motif-based graph analysis has attracted much attention due to its efficacy in tasks such as clustering, ranking, and link prediction. These tasks require Network Motif Discovery (NMD) at the early stage to identify the motifs of G. However, existing NMD solutions have two drawbacks: (1) Lack of theoretical guarantees on the quality of the samples generated using the existing methods, and (2) inefficient algorithms, which are not scalable for large graphs. These limitations hinder the exploration of motifs for analyzing large graphs. To address the above issues, we propose a novel solution named MOSER ( MO tif Discovery using SER ial Test). This novel NMD framework leverages a significance testing method known as the serial test, which differs from the existing solutions. We further propose two fast incremental subgraph counting algorithms, allowing MOSER to scale to larger graphs than ever possible before. Extensive experimental results show that using MOSER can improve the state-of-the-art up to 5 orders of magnitude in efficiency and that the motifs found by MOSER facilitate downstream tasks such as link prediction.

Road network applications, such as navigation, incident detection, and Point-of-Interest (POI) recommendation, make extensive use of network edge weights (e.g., traveling times). Some of these weights can be missing, especially in a road network where traffic data may not be available for every road. In this paper, we study the stochastic weight completion (SWC) problem, which computes the weight distributions of missing road edges. This is difficult, due to the intricate temporal and spatial correlations among neighboring edges. Moreover, the road network can be sparse, i.e., there is a lack of traveling information in a large portion of the network. To tackle these challenges, we propose the Contextual Graph Completion (ConGC). We propose to incorporate the contextual properties about the road network (e.g., speed limits, number of lanes, road types) to provide finer granularity of spatial correlations. Moreover, ConGC incorporates temporal and periodic dimensions of the road traffic. We evaluate ConGC against existing methods on three real road network datasets. They show that ConGC is more effective and efficient than state-of-the-art solutions.

Path-based solutions have been shown to be useful for various graph analysis tasks, such as link prediction and graph clustering. However, they are no longer adequate for handling complex and gigantic graphs. Recently, motif-based analysis has attracted a lot of attention. A motif, or a small graph with a few nodes, is often considered as a fundamental unit of a graph. Motif-based analysis captures high-order structure between nodes, and performs better than traditional "edge-based" solutions. In this paper, we study motif-path , which is conceptually a concatenation of one or more motif instances. We examine how motif-paths can be used in three path-based mining tasks, namely link prediction, local graph clustering and node ranking. We further address the situation when two graph nodes are not connected through a motif-path, and develop a novel defragmentation method to enhance it. Experimental results on real graph datasets demonstrate the use of motif-paths and defragmentation techniques improves graph analysis effectiveness.

Graph databases witness the rise of Graph Query Language (GQL) in recent years, which enables non-programmers to express a graph query. However, the current solution does not support motif-related queries on knowledge graphs, which are proven important in many real-world scenarios. In this paper, we propose a GQL framework for mining knowledge graphs, named M-Cypher. It supports motif-related graph queries in an effective, efficient and user-friendly manner. We demonstrate the usage of the system by the emerging Covid-19 knowledge graph analytic tasks.

Incident detection (ID), or the automatic discovery of anomalies from road traffic data (e.g., road sensor and GPS data), enables emergency actions (e.g., rescuing injured people) to be carried out in a timely fashion. Existing ID solutions based on data mining or machine learning often rely on dense traffic data; for instance, sensors installed in highways provide frequent updates of road information. In this paper, we ask the question: Can ID be performed on sparse traffic data (e.g., location data obtained from GPS devices equipped on vehicles)? As these data may not be enough to describe the state of the roads involved, they can undermine the effectiveness of existing ID solutions. To tackle this challenge, we borrow an important insight from the transportation area, which uses trajectories (i.e., moving histories of vehicles) to derive incident patterns. We study how to obtain incident patterns from trajectories and devise a new solution (called Filter-Discovery-Match (FDM)) to detect anomalies in sparse traffic data. Experiments on a taxi dataset in Hong Kong and a simulated dataset show that FDM is more effective than state-of-the-art ID solutions on sparse traffic data.

In graph applications (e.g., biological and social networks), various analytics tasks (e.g., clustering and community search) are carried out to extract insight from large and complex graphs. Central to these tasks is the counting of the number of motifs , which are graphs with a few nodes. Recently, researchers have developed several fast motif counting algorithms. Most of these solutions assume that graphs are deterministic, i.e., the graph edges are certain to exist. However, due to measurement and statistical prediction errors, this assumption may not hold, and hence the analysis quality can be affected. To address this issue, we examine how to count motifs on uncertain graphs, whose edges only exist probabilistically. Particularly, we propose a solution framework that can be used by existing deterministic motif counting algorithms. We further propose an approximation algorithm. Extensive experiments on real datasets show that our algorithms are more effective and efficient than existing solutions.

Communities are prevalent in social networks, knowledge graphs, and biological networks. Recently, the topic of community search (CS) has received plenty of attention. The CS problem aims to look for a dense subgraph that contains a query vertex. Existing CS solutions do not consider the spatial extent of a community. They can yield communities whose locations of vertices span large areas. In applications that facilitate setting social events (e.g., finding conference attendees to join a dinner), it is important to find groups of people who are physically close to each other, so it is desirable to have aspatial-aware community(or SAC), whose vertices are close structurally and spatially. Given a graph$G$and a query vertex$q$, we develop an exact solution to find the SAC containing$q$, but it cannot scale to large datasets, so we design three approximation algorithms. We further study the problem of continuous SAC search on a “dynamic spatial graph,” whose vertices’ locations change with time, and propose three fast solutions. We evaluate the solutions on both real and synthetic datasets, and the results show that SACs are better than communities returned by existing solutions. Moreover, our approximation solutions perform accurately and efficiently.

International audience

Communities are prevalent in social networks, knowledge graphs, and biological networks. Recently, the topic of community search (CS) has received plenty of attention. Given a query vertex, CS looks for a dense subgraph that contains it. Existing CS solutions do not consider the spatial extent of a community. They can yield communities whose locations of vertices span large areas. In applications that facilitate the creation of social events (e.g., finding conference attendees to join a dinner), it is important to find groups of people who are physically close to each other. In this situation, it is desirable to have a spatial-aware community (or SAC), whose vertices are close structurally and spatially. Given a graph G and a query vertex q , we develop exact solutions for finding an SAC that contains q . Since these solutions cannot scale to large datasets, we have further designed three approximation algorithms to compute an SAC. We have performed an experimental evaluation for these solutions on both large real and synthetic datasets. Experimental results show that SAC is better than the communities returned by existing solutions. Moreover, our approximation solutions can find SACs accurately and efficiently.