The evaluation of Kleene Closure Property Path Queries (KPPQs) over RDF graphs presents a fundamental trade-off. Under the intuitive simple path semantics, which forbids node repetition, the problem is NP-complete. This forces practical systems to adopt existential path semantics, which admits tractable evaluation but produces result sets bloated with redundant and often semantically meaningless paths due to unnecessary detours through cycles. This paper introduces a novel indexing framework that effectively navigates this trade-off. Our key insight is that while enumerating all simple paths is intractable, a carefully selected, compact set of representative simple paths is sufficient to correctly and completely answer connectivity queries in practice. We propose the Node Clustered Index (NCI), which pre-materializes such paths—including the longest acyclic chains and fundamental cycles —transforming online query processing from a costly graph traversal into an efficient index lookup and expansion operation. Crucially, our method guarantees that every result conforms to simple path semantics. Extensive experiments demonstrate that our approach achieves near-perfect recall, outperforming state-of-the-art systems by up to an order of magnitude. This work establishes that for NP-complete path problems, seeking polynomial-time, empirically perfect approximations is a viable and powerful paradigm, delivering both performance and quality without compromise.

Recently, Graph Foundation Models (GFMs) have emerged as a central focus in the field of graph learning due to their strong generalizability to various unseen graphs. However, existing GFMs typically work under the homophily assumption, and the exploration of universality on heterophilic graphs is still in its early stages. In fact, even in homophilic graphs, there exists limited yet informative heterophilic information that is not fully exploited by current GFMs. Moreover, due to the requirement for universality, the heterophily issue faced by GFMs is more challenging than in classical graph learning, as it requires training a single model to adapt to varying structures, features, and tasks. Classic heterophilic graph learning methods primarily based on the node-level homophily or heterophily. However, we highlight that homophily and heterophily exist not only at the node semantic level, but also at a finer granularity across individual feature dimensions. This finding enables GFMs to adapt to heterophilic graphs and better utilize the small amount of heterophilic information in homophilic graphs. Based on this, we propose Topology-aware Feature Sorting Graph Foundation Model (TFSGFM), which employs a feature-level topology-aware sorting strategy and a dual-channel graph neural network framework, enabling unified modeling of both feature and structure. Extensive experiments demonstrate the strong generalizability of TFSGFM. The source code is available at https://github.com/hedongxiao-tju/TFSGFM.

Logical rules have been widely used for expressing schema knowledge in various practical applications. It is infeasible to handcraft rules from large knowledge graphs (KGs) and thus many methods have been proposed for learning rules automatically from KGs. However, it is largely ignored how to extract rules in a (target) KG from rules that already exist in some other (source) KGs. In this paper, we propose a framework for KG rule learning based on transfer learning. A major challenge for establishing such a framework is that a suitable alignment mechanism is required for mapping certain subgraph structures between predicates in the source KG and the target KG. Hence, our framework provides a new method for predicate mapping based on graph-structural similarity. The proposed framework can be used as a standalone rule learner but more importantly, it paves a new way for enhancing the state-of-the-art rule learners for large KGs. Extensive experiments are conducted to evaluate the new approach to rule learning, which shows that rules in smaller KGs can be effectively transferred to a large KG.

Contrastive Learning (CL) has emerged as a popular self-supervised representation learning paradigm that has been shown in many applications to perform similarly to traditional supervised learning methods. A key component of CL is mining the latent discriminative relationships between positive and negative samples and using them as self-supervised labels. We argue that this discriminative contrastive task is, in essence, similar to a classification task, and the “either positive or negative” hard label sampling strategies are arbitrary. To solve this problem, we explore ideas from data distillation, which considers probabilistic logit vectors as soft labels to transfer model knowledge. We attempt to abandon the classical hard sampling labels in CL and instead explore self-supervised soft labels. We adopt soft sampling labels that are extracted, without supervision, from the inherent relationships in data pairs to retain more information. We propose a new self-supervised graph learning method, Distill and Contrast (D&C), for learning representations that closely approximate natural data relationships. D&C extracts node similarities from the features and structures to derive soft sampling labels, which also eliminate noise in the data to increase robustness. Extensive experimental results on real-world datasets demonstrate the effectiveness of the proposed method.

Traditional recommendation systems focus on maximizing user satisfaction by suggesting their favorite items. This user-centric approach may lead to unfair exposure distribution among the providers. On the contrary, a provider-centric design might become unfair to the users. Therefore, this paper proposes a re-ranking model FairSort1to find a trade-off solution among user-side fairness, provider-side fairness, and personalized recommendations utility. Previous works habitually treat this issue as a knapsack problem, incorporating both-side fairness as constraints. In this paper, we adopt a novel perspective, treating each recommendation list as a runway rather than a knapsack. In this perspective, each item on the runway gains a velocity and runs within a specific time, achieving re-ranking for both-side fairness. Meanwhile, we ensure the Minimum Utility Guarantee for personalized recommendations by designing a Binary Search approach. This can provide more reliable recommendations compared to the conventional greedy strategy based on the knapsack problem. We further broaden the applicability of FairSort, designing two versions for online and offline recommendation scenarios. Theoretical analysis and extensive experiments on real-world datasets indicate that FairSort can ensure more reliable personalized recommendations while considering fairness for both the provider and user.

In graph anomaly detection (GAD), the fact that anomalous nodes usually exhibit high heterophily, while most Graph Neural Networks (GNNs) have homophily assumptions, leads to poor performance. Many studies have attempted to solve this problem by employing a set of graph filters covering various frequencies. Their ultimate goal is to design the most appropriate spectral filter to capture the complex signals generated by normals and anomalies. The critical aspect lies in the fusion of information from filters with different frequency response functions. However, existing methods lack a clear indicator to guide the fusion of information at different frequencies. In this paper, we find that local homophily is a valuable metric for assessing the weights of high- and low-frequency information at the node level, and explicitly point out that the accuracy of local homophily is positively correlated with the accuracy of anomaly detection. Moreover, we unveil the phenomenon of camouflage in anomalous, wherein these nodes disguise themselves by making their features resemble those of surrounding normals.

Our research reveals that multi-interest recommendation models in the matching stage tend to exhibit an under-clustered item embedding space, which leads to a low discernibility between items and hampers item retrieval. This highlights the necessity for item embedding enhancement. However, item attributes, which serve as effective side information for enhancement, are either unavailable or incomplete in many public datasets due to the labor-intensive nature of manual annotation tasks. This dilemma raises two meaningful questions: 1. Can we bypass manual annotation and directly simulate complete attribute information from the interaction data? And 2. If feasible, how can we simulate attributes with high accuracy and low complexity in the matching stage?

Multi-interest recommendation methods extract multiple interest vectors to represent the user comprehensively. Despite their success in the matching stage, previous works overlook the long-tail problem. This results in the model excelling at suggesting head items, while the performance for tail items, which make up more than 70% of all items, remains suboptimal. Hence, enhancing the tail item recommendation capability holds great potential for improving the performance of the multi-interest model.

Network embedding which is to learn a low dimensional representation of nodes in a network has been used in many network analysis tasks. Some network embedding methods, including those based on Generative Adversarial Networks (GAN) (a promising deep learning model), have been proposed recently. Existing GAN-based methods typically use GAN to learn a Gaussian distribution as a prior for network embedding, which makes it difficult to distinguish the node representation from Gaussian distribution. It did not apply the adversarial learning strategy on the representation mechanism but just on representation results. Thus, it does not make full use of the essential advantage of GAN, and leads to compromised performance of the method. To address this problem, we propose a novel adversarial learning framework consisting of three players for network embedding, which applies the adversarial learning strategy on the representation mechanism, called Adversarial representation mechanism GAN (ArmGAN). Specifically, the first two players, named encoder and competitor, aim to learn two different representation mechanisms (i.e., two ways projecting data onto latent space). They compete with each other to improve their representation mechanisms. The third player is the discriminator, which discriminate the representation mechanism of the encoder from that of the competitor. In addition, we design a perturbation strategy to produce fake networks from the original network, and feed the fake networks to the competitor to obtain a “fake” representation mechanism. We evaluated ArmGAN on a variety of tasks including node clustering, node classification, link prediction and visualization. Moreover, we compared ArmGAN with 10 state-of-the-art methods (including DGI, which is well-known for its high accuracy) on 7 real-world networks. The experimental results show the significant superiority of ArmGAN over the existing methods.

In recent years, as the demand for senior care services has further increased, it has become more difficult to obtain matching services from the vast amount of data. Therefore, this paper proposes a service recommendation framework PCE-CF based on an embedded user portrait model. The framework accurately describes the elderly users through four dimensions—population, society, consumption, and health—and constructs the user portrait model by embedding tags. The embedded vector of each older man is learned through the deep learning model, and different feature groups are meaningfully expressed in the transformation space. In addition, location context and dynamic interest model are introduced to process embedded vectors, and users' service preferences are predicted according to their dynamic behaviors. The experiment results show that the PCE-CF framework proposed in this paper can improve the recommendation algorithm's efficiency and have higher feasibility in personalized service recommendations.

In this paper, we study the problem of part-of-speech (POS) tagging for security vulnerability descriptions (SVD). In contrast to newswire articles, SVD often contains a high-level natural language description of the text composed of mixed language studded with codes, domain-specific jargon, vague language, and abbreviations. Moreover, training data dedicated to security vulnerability research is not widely available. Existing neural network-based POS tagging has often relied on manually annotated training data or applying natural language processing (NLP) techniques, suffering from two significant drawbacks. The former is extremely time-consuming and requires labor-intensive feature engineering and expertise. The latter is inadequate to identify linguistically-informed words specific to the SVD domain. In this paper, we propose an automatic approach to assign POS tags to tokens in SVD. Our approach uses the character-level representation to automatically extract orthographic features and unsupervised word embeddings to capture meaningful syntactic and semantic regularities from SVD. The character level representations are then concatenated with the word embedding as a combined feature, which is then learned and used to predict the POS tagging. To deal with the issue of the poor availability of annotated security vulnerability data, we implement a finetuning approach. Our approach provides public access to a POS annotated corpus of ~8M tokens, which serves as a training dataset in this domain. Our evaluation results show a significant improvement in accuracy (17.72%-28.22%) of POS tagging in SVD over the current approaches.

Abstract Ontology-mediated querying (OMQ) provides a paradigm for query answering according to which users not only query records at the database but also query implicit information inferred from ontology. A key challenge in OMQ is that the implicit information may be infinite, which cannot be stored at the database and queried by off -the -shelf query engine. The commonly adopted technique to deal with infinite entailments is query rewriting, which, however, comes at the cost of query rewriting at runtime. In this work, the partial materialization method is proposed to ensure that the extension is always finite. The partial materialization technology does not rewrite query but instead computes partial consequences entailed by ontology before the online query. Besides, a query analysis algorithm is designed to ensure the completeness of querying rooted and Boolean conjunctive queries over partial materialization. We also soundly and incompletely expand our method to support highly expressive ontology language, OWL 2 DL. Finally, we further optimize the materialization efficiency by role rewriting algorithm and implement our approach as a prototype system SUMA by integrating off-the-shelf efficient SPARQL query engine. The experiments show that SUMA is complete on each test ontology and each test query, which is the same as Pellet and outperforms PAGOdA. Besides, SUMA is highly scalable on large datasets.

The study of paraconsistent reasoning with ontologies is especially important for the Semantic Web since knowledge is not always perfect within it. However, classical OWL reasoners cannot support reasoning with inconsistent ontologies. In this article, the authors present a plugin-based framework called prose to provide rich paraconsistent reasoning services for OWL ontologies, whose architecture contains the three following parts: a classical OWL reasoner, a multi-valued transformer, and an OWL API connecting with them. Within the proposed framework prose, they implement different multi-valued paraconsistent reasoning in the OWL. Moreover, they select three popular classical OWL reasoners and two typical kinds of reasoning services for users. As the authors excepted, prose does exactly enable current classical OWL reasoners to tolerate inconsistency in a simple and convenient way. Finally, they evaluate the three reasoners in a united framework (prose) and, as a result, those results can amend the analysis of the three reasoners on inconsistent ontologies.

In this paper, we present a federated path querying language (FPQ) as itself an extension of the nested regular path querying language with adding an axis operator to support the federation of RDF dataset and relational database. We have proven that FPQ has more expressive power than the nested regular path query language (not to mention regular path querying language). It enjoys the same computational complexity as the regular path query language and its additional expressivity can be exactly used to characterize the conjunction and federation of nested regular path queries. Moreover, we discuss the expressivity of various fragments of FPQ and implement FPQ. Finally, we present an application scenario related to the car-pooling services in real life.

In this paper, we analyze some basic features of SPARQL queries from practical world in a statistical way. In particular, we focus on three statistic features including the occurrence frequency of triple patterns, fragments, and well-designed patterns and four semantic features including monotonicity, non-monotonicity, weak monotonicity and satisfiability. All the features contribute to characterize SPARQL queries in different dimensions. We hope that this statistical analysis would provide some useful observations for researchers and engineers who are interested in what real-word SPARQL queries look like, so that they could develop some practical heuristics for processing SPARQL queries, as well as build SPARQL query processing engines and benchmarks. In addition, our research facilitates to reduce scope of the problems by avoiding some cases that may not occur in practice.