While large language models have revolutionized Text-to-SQL tasks, translating natural language into Graph Query Languages (Text2GQL) remains underexplored due to the topological heterogeneity and syntactic diversity of graph query languages (e.g., Cypher, Gremlin, SPARQL).Existing approaches often struggle with structural hallucinations and lack adaptability in cold-start scenarios.In this paper, we present a unified, trainingfree Text2GQL framework.First, Structural Twig Linking elevates schema grounding to the identification of semantic substructures ("twigs"), providing robust topological priors.Second, addressing data scarcity, Evolutionary In-Context Learning operates in a Tabula Rasa setting to implicitly construct a selfgrowing repository of verified examples driven by syntactic utility.Finally, our Adversarial Execution-Guided Correction agent enforces fidelity through synergistic static critique and dynamic verification.Experiments demonstrate significant improvements over baselines in both accuracy and executability across diverse GQLs.The code is available at https: //github.com/nf202/Text2Graph.

Graph database systems play a vital role in graph structure analysis across a wide range of application domains. Queries with set-level constraints on community structures are increasingly demanded in real-world applications. However, existing graph databases lack native support for both efficient monadic second-order logic (MSOL) query processing and fast community retrieval, hindering their applicability to such analytical tasks. In this paper, we present Monac- Graph, a graph database system that enables practical MSOL queries. MonacGraph features an efficient two-phase execution engine that minimizes redundant first-order clause evaluations. We propose SO-Gremlin, an extension of the Gremlin graph traversal language with intuitive syntax for set quantification. The system adopts LSM-Community as its storage backend, enabling efficient queries over precomputed graph structures. Additionally, MonacGraph provides a user-friendlyWeb interface for composing complex set-level queries and visualizing results in real time. A demonstration video can be found at https://www.youtube.com/watch?v=Eezdq9tzbJE.

With the rapid growth of Web-based academic publications, more and more papers are being published annually, making it increasingly difficult to find relevant prior work. Citation prediction aims to automatically suggest appropriate references, helping scholars navigate the expanding scientific literature. Here we present CiteRAG, the first comprehensive retrieval-augmented generation (RAG)-integrated benchmark for evaluating large language models on academic citation prediction, featuring a multi-level retrieval strategy, specialized retrievers, and generators. Our benchmark makes four core contributions: (1) We establish two instances of the citation prediction task with different granularity. Task 1 focuses on coarse-grained list-specific citation prediction, while Task 2 targets fine-grained position-specific citation prediction. To enhance these two tasks, we build a dataset containing 7,267 instances for Task 1 and 8,541 instances for Task 2, enabling comprehensive evaluation of both retrieval and generation. (2) We construct a three-level large-scale corpus with 554k papers spanning many major subfields, using an incremental pipeline. (3) We propose a multi-level hybrid RAG approach to citation prediction, fine-tuning embedding models with contrastive learning to capture complex citation relationships, paired with specialized generation models. (4) We conduct extensive experiments across state-of-the-art language models, including closed-source APIs, open-source models, and our fine-tuned generators, demonstrating the effectiveness of our framework. Our open-source toolkit enables reproducible evaluation and focuses on academic literature, providing the first comprehensive evaluation framework for citation prediction and serving as a methodological template for other scientific domains. Our source code and data are released at https://github.com/LQgdwind/CiteRAG.

With the widespread adoption of collaborative filtering techniques for personalized recommendations, exposure bias has become a significant challenge.Exposure biasrefers to the tendency of recommendation models to disproportionately favor items with high exposure over those with low exposure. In graph collaborative filtering that uses graph neural networks (GNNs) for recommendations, exposure bias can be exacerbated due to 1) the reliance on positive feedback during graph construction and 2) the effects of the neighbor aggregation step in GNNs. To tackle this challenge, we propose a novel and efficient framework called FUGCF (training-Free andUnbiasedGraphCollaborativeFiltering) to improve both the accuracy and bias mitigation of graph-based personalized recommendations. FUGCF employs a two-stage calculation strategy: it estimates exposure probabilities in the first stage and then leverages them to help derive debiased node embeddings in the second stage. Furthermore, we design a training-free estimation method for FUGCF based on closed-form solutions to enhance its computational efficiency. The extensive experiments on a synthetic dataset and three real-world datasets demonstrate the effectiveness of FUGCF in reducing exposure bias, improving recommendation accuracy, and optimizing computational efficiency.

Recommender systems are increasingly prevalent to provide personalized suggestions and enhance user satisfaction. Typical recommendation models encode users and items as embeddings, and generate recommendations by assessing the similarity between these embeddings. Despite their effectiveness, these embedding-based models struggle with modeling user uncertainty and capturing diverse user interests using a single fixed user embedding. Recent studies have begun to explore a user-distribution paradigm to learn distributions for users. However, this approach employs a single distribution per user, which fails to effectively delineate semantic boundaries, resulting in sub-optimal recommendations. To this end, we propose GCDR, a Guided Conditional Diffusion Recommender model, to learn multiple distributions for each user in this paper. Specifically, GCDR addresses two major challenges: 1) learning disentangled distributions, and 2) learning personalized distributions. GCDR captures inter-user and intra-user distribution properties through conditional and guided diffusion, respectively. It maintains user-specific embeddings to encode long-term interests for conditional diffusion, while for guided diffusion, it incorporates short-term interests encoded from recent interactions with category preferences. To align the diffusion model with the recommendation task, we train GCDR with three loss functions, included the user loss, the recommendation loss and the diffusion loss. Extensive experiments on four real-world datasets show that GCDR is able to learn effective user distributions and is superior to thirteen state-of-the-art baseline methods.

Temporal knowledge graph completion aims to predict missing facts in a knowledge graph by leveraging temporal information. Existing methods often struggle to capture both the long-term changes and short-term variability of relations, which are crucial for accurate prediction. In this paper, we propose a novel method called TeRDy for temporal knowledge graph completion. TeRDy captures temporal relational dynamics by utilizing time-invariant embeddings, along with long-term temporally dynamic embeddings (e.g., enduring political alliances) and short-term temporally dynamic embeddings (e.g., transient political events). These two types of embeddings are derived from low- and high-frequency components via frequency decomposition. Also, we design temporal smoothing and temporal gradient to seamlessly incorporate timestamp embeddings into relation embeddings. Extensive experiments on benchmark datasets demonstrate that TeRDy outperforms state-of-the-art temporal knowledge graph embedding methods.

Multi-model databases and polystore systems are increasingly studied for managing multimodel data holistically.As their primary interface, multi-model query languages (MMQLs) often exhibit complex grammars, highlighting the need for effective Text-to-MMQL translation methods.Despite advances in natural language translation, no effective solutions for Text-to-MMQL exist.To address this gap, we formally define the Text-to-MMQL task and present the first Text-to-MMQL dataset involving three representative MMQLs.We propose an adaptive Text-to-MMQL framework that includes both a schema embedding module for capturing multi-model schema information and an MMQL representation strategy to generate concise intermediate query formats with error correction in generated queries.Experimental results show that the proposed framework achieves over a 9% accuracy improvement over our adapted baseline methods.

Graph embedding aims to extract low-dimensional representation vectors, commonly referred to as embeddings, from graph data. The generated embeddings simplify subsequent data analysis and machine learning tasks. Recently, researchers have proposed the use of contrastive learning on graphs to extract node embeddings in an unsupervised manner. Although existing graph contrastive learning methods have significantly advanced this field, there is still potential for further exploration, particularly in optimizing training efficiency and enhancing embedding quality. In this paper, we propose an efficient unsupervised graph embedding method named GEARED. First, the method involves an attributed graph reduction module that converts the raw graph into a reduced graph, greatly improving training efficiency. Second, GEARED employs a dual-level loss with adaptive scaling factors to obtain high-quality embeddings. Experimental results demonstrate that GEARED achieves high classification accuracy, good scalability, and enhanced embedding quality.

Subgraph matching is a fundamental operation in graph data management and facilitates the analysis of complex datasets in various domains such as computer vision, bioinformatics, and social networks. With the scale of graph data getting larger and larger, the performance of subgraph matching algorithms is facing significant challenges. However, existing tools are not efficient enough for subgraph matching tasks. In this paper, we present a subgraph matching tool called RAISIN. To improve the efficiency of subgraph matching tasks, RAISIN accelerates the algorithms of the matching engine with community-structure-based and parallelism optimization. Moreover, to improve user-friendliness, RAISIN provides a graphical user interface to monitor the matching process and visualize matching results. Finally, three use cases are presented to demonstrate the efficiency and user-friendliness of RAISIN.

Recently, several social network analysis algorithms have been optimized by leveraging the community structure commonly found in graphs. Since community structure is fun-damental to these algorithms, storing graphs based on their community structure can significantly enhance the performance of graph algorithms that rely on it for optimization. However, existing graph storage systems do not natively store graphs according to the community structure, which limits their per-formance in retrieving communities. To fill this gap, we pro-pose LSM-Community, a graph storage system inspired by the LSM - Tree design that stores graphs on disk based on their community structure. To dynamically maintain the community structure during graph updates, we present the community-centric dynamic community detection algorithm$(C^{3}D)$. Experimental results demonstrate that LSM-Community outperforms other storage systems in classical community discovery tasks (e.g., performing CD on UK-2007 dataset with LSM-Community is$86.12\times$faster than Neo4j) while maintaining high performance on classical graph analytic algorithms. This indicates that LSM-Community efficiently supports community discovery and query processing while preserving the performance of classical analytic algorithms,

The heterogeneous graph, as an effective representation of real-world data, encapsulates rich structural and semantic information. In recent years, numerous Heterogeneous Graph Neural Networks (HGNNs) have been proposed to learn node representations on heterogeneous graphs. Although existing methods have introduced various unique information aggregation and semantic fusion mechanisms, they still exhibit limitations in effectiveness and scalability. In this study, we introduce the gatekeeping theory in heterogeneous graph learning and investigate the primary challenges limiting current HGNNs. To address these challenges, we propose a novel, effective, and scalable heterogeneous graph neural network framework, the Heterogeneous Convolution-oriented Attention Network (HCAN). HCAN enhances the heterogeneous attention mechanism to learn far-sighted weights by encoding long-range relation information into node representation with a convolutional subgraph encoder. To further improve heterogeneous graph representation learning, we propose effective and scalable models based on the HCAN framework. We evaluate HCAN on various commonly used heterogeneous datasets and show that it outperforms the state-of-the-art methods, especially on challenging datasets.

Owing to the capability of in-context learning, large language models (LLMs) have shown impressive performance across diverse mathematical reasoning benchmarks. However, we find that few-shot demonstrations can sometimes bring negative performance and their effectiveness on LLMs’ reasoning abilities remains unreliable. To this end, in this paper, we aim to theoretically analyze the impact of in-context demonstrations on LLMs’ reasoning performance. We prove that the reasoning efficacy (measured by empirical prediction loss) can be bounded by an LLM-oriented semantic similarity and an inference stability of demonstrations, which is general for both one-shot and few-shot scenarios. Based on this finding, we propose a straightforward, generalizable, and low-complexity demonstration selection method named LMS3. It facilitates to select the most pertinent samples for different LLMs and includes a novel demonstration rejection mechanism to automatically filter out samples that are unsuitable for few-shot learning. Through experiments on three representative benchmarks, two LLM backbones, and multiple few-shot settings, we verify that our LMS3 has superiority and achieves consistent improvements on all datasets, which existing methods have been unable to accomplish. Our code is available at https://github.com/Ljyustc/LMS3.

Traditional recommender systems have relied heavily on positive feedback for learning user preferences, while the abundance of negative feedback in real-world scenarios remains underutilized. To address this limitation, recent years have witnessed increasing attention on leveraging negative feedback in recommender systems to enhance recommendation performance. However, existing methods face three major challenges: limited model compatibility, ineffective information exchange, and computational inefficiency. To overcome these challenges, we propose a model-agnostic Signed Dual-Channel Graph Contrastive Learning (SDCGCL) framework that can be seamlessly integrated with existing graph contrastive learning methods. The framework features three key components: (1) a Dual-Channel Graph Embedding that separately processes positive and negative graphs, (2) a Cross-Channel Distribution Calibration mechanism to maintain structural consistency, and (3) an Adaptive Prediction Strategy that effectively combines signals from both channels. Building upon this framework, we further propose a Dual-channel Feedback Fusion (DualFuse) model and develop a two-stage optimization strategy to ensure efficient training. Extensive experiments on four public datasets demonstrate that our approach consistently outperforms state-of-the-art baselines by substantial margins while exhibiting minimal computational complexity. Our source code and data are released at \url{https://github.com/LQgdwind/nips25-sdcgcl}.

Recent advances in graph contrastive learning (GCL) have significantly enhanced recommendation systems. However, most existing approaches predominantly focus on optimizing training data fit while overlooking exposure bias, a critical issue that can substantially impact recommendation effectiveness. Drawing inspiration from sociological theories of human interaction patterns-specifically how individuals balance self-presentation and self-hiding behaviors in social contexts-this paper proposes BPH4Rec, a novel Balancing self-Presentation and self-Hiding approach for exposure-aware Recommendation based on GCL. Within the GCL framework, BPH4Rec introduces two complementary mechanisms: (1) a self-hiding mechanism that modifies the adjacency matrix of contrastive views through custom inverse propensity scoring (IPS), effectively addressing exposure bias, and (2) a self-presentation mechanism that incorporates densification factors during matrix reconstruction to mitigate sparsity-induced biases. Through extensive evaluation on six public benchmark datasets, BPH4Rec demonstrates substantial improvements over state-of-the-art baselines, particularly in promoting long-tail item discovery while maintaining recommendation accuracy.

Procedural Language extensions of SQL (abbr. PL/SQL) enhance database programming by integrating procedural constructs with SQL's declarative syntax, thereby improving the reusability, modularity, and maintainability of SQL. Besides, PL/SQL in database systems presents significant challenges in real-world development, primarily due to the inherent complexity of programming. To reduce the development difficulty of PL/SQL, this paper studies the novel task of translating natural language (NL) to PL/SQL (i.e., NL-to-PL/SQL), aimed at simplifying PL/SQL development. Recent advancements in language models have shown promise in translating natural language questions into SQL queries (i.e., Text-to-SQL). However, the state-of-the-art Text-to-SQL methods focus only on single SQL queries, neglecting the procedural extensions of SQL, which limits their effectiveness for the NL-to-PL/SQL task. In this paper, we propose PLForge, a suite of pre-trained language models with parameter configurations of 3B, 7B, and 15B, tailored for NL-to-PL/SQL tasks. To enhance the PL/SQL generation capabilities of PLForge, we leverage a curated PL/SQL-centric data corpus and employ an incremental pre-training approach. Furthermore, to fully exploit the potential of PLForge, we propose a comprehensive prompt construction strategy tailored specifically for PL/SQL. Given the scarcity of NL-to-PL/SQL datasets, we develop a template-based method for generating NL-to-PL/SQL data. We conduct a series of experiments on PLForge and several baseline models. Based on execution match and exact match metrics that are designed specifically for the NL-to-PL/SQL task, the experimental results demonstrate that PLForge outperforms existing models in both in-context learning and supervised fine-tuning settings.

With the wide application of graphs in various fields, graph query languages have attracted more and more attention. Existing graph query languages, such as GraphQL and SoQL, mostly have similar expressive power as the first-order logic or its extended versions, and are limited when used to express various queries. In this paper, since the graph data model is the base of the graph query language, we propose a new graph data model with the expressive power of monadic second-order logic (abbr. MSOL), and then present a more expressive SQL-like declarative graph query language named$SOGQL$to support more common queries efficiently. Specifically, a new graph calculus is first proposed based on MSOL for attributed graphs. Then, the new graph data model is proposed. Its graph algebra, which operates on graph sets, has seven fundamental operators such as union, filter, map, and reduce. Next, the graph query language$SOGQL$is proposed based on the graph data model. Since the graph algebra has the same expressive power as the graph calculus,$SOGQL$has the expressive power of MSOL, and can express queries with constraints on subgraphs. Moreover, applied with$SOGQL$, a prototype system named$SOGDB$is implemented.$SOGDB$is applied with$SOGQL$, and the experimental results show its efficiency.

Recommender systems mitigate information overload by offering personalized suggestions to users. As the interactions between users and items can inherently be depicted as a bipartite graph, recent years have seen a surge in the interest in harnessing graph neural networks (GNNs) for enhancing recommender systems. However, a notable limitation of current GNN-based recommendation models is their exclusive emphasis on positive feedback, while disregarding the potentially insightful negative feedback. In this article, we introduce Pone-GNN, a novel recommendation model that synergistically integrates both Po sitive and ne gative feedback in G raph N eural N etworks. Pone-GNN utilizes dual embeddings–interest embeddings for capturing a user’s likes and disinterest embeddings for a user’s dislikes. Also, Pone-GNN performs message passing for both positive and negative feedback, and integrates two sets of embeddings through contrastive learning, which is crucial for extracting robust and discriminative embeddings. Our comprehensive experimental analysis demonstrates that Pone-GNN outperforms state-of-the-art models on diverse real-world recommendation datasets. For example, Pone-GNN achieves a 6.15% increase in relative nDCG@10 compared to the runner-up on the KuaiRec dataset.

To analyze and process graph data, researchers have proposed Graph Neural Network (GNN) models. In this paper, we focus on methods for boosting the performance of existing GNN models and propose GraphHI, a GNN framework that integrates Hidden Insights to enhance the performance of a given GNN model. We propose to utilize both inter-model and intra-model hidden insights. The inter-model hidden insights encompass the embedding vectors and logit vectors derived from other pretrained models using the same graph data. The intra-model hidden insights incorporate the embedding vectors of other nodes from the same GNN model. To optimize the suitability of hidden insights for GNN model training, we conduct a theoretical analysis of the influence of various forms of the transformed logits and the parameter$T$in the data transformation function. Based on this analysis, a method for setting dynamic personalized parameters in the data transformation is proposed, which is tailored to the current state of each node in the GNN model. To integrate multiple sources of hidden insights, we propose ALC, an algorithm that dynamically sets appropriate combination coefficients for various loss terms. The experimental results show that GraphHI can boost the performance of GNN models using different pretrained models in four different tasks.

Contrastive learning, a powerful self-supervised learning paradigm, has shown its efficacy in learning embed dings from independent and identically distributed (IID) as well as non-IID data without relying on label information. Since high-quality discriminative embeddings form a rich embedding space, which benefits model performance on downstream tasks, it is necessary to study how to improve the quality of contrastive node embeddings in graph contrastive learning. However, there has been limited research on this area. In this paper, we investigate how to generate high-quality contrastive node embeddings based on an in-depth analysis of graph contrastive losses. Firstly, we propose a novel and effective method, GLATE, for estimating the temperatures in three mainstream graph contrastive losses during the training phase. Secondly, we conduct the derivation of GLATE, and the derivation results reveal the specific relationship between the quality of contrastive node embeddings and tem-peratures. Finally, the extensive experiments on 16 benchmark datasets demonstrate that GLATE consistently outperforms the state-of-the-art graph contrastive learning models in terms of both model performance and training efficiency.

The concept of polystore has been proposed and studied for heterogeneous data storage and cross-model query processing. Correspondingly, the evaluation of diverse polystores is an essential yet challenging task. However, most current evaluation approaches for polystores only focus on cross-model analytical workloads and provide limited configurations. To address these problems, this paper presents a flexible polystore evaluation platform named FONT. FONT incorporates hybrid single-model and cross-model workloads that combine read and write operations, as well as diagnostic analytical workloads. FONT supports customization of both multi-model dataset generation and workload generation procedures. The proposed platform is the first visual tool for polystore evaluation, providing user-friendly graphical interfaces for user customization and displaying evaluation results.

Synthetic graph datasets are crucial for the assessment of network analysis algorithms, providing a measure of their effectiveness and efficiency. However, most existing generation techniques typically focus on community formation, neglecting the fact that real-world communities not only emerge but may also dissipate over time. This lifecycle occurs within a finite timeframe, adding complexity to the community dynamics. In this paper, firstly we introduce the concept of time-bound community to characterize communities that are destined to disintegrate. Secondly, we devise GTB, a temporal graph Generation method featuring Time-Bound communities, leveraging newly identified patterns within real datasets that we have collected. Additionally, we propose the advanced Temporal Edge Distribution (TED) model, a key component of G TB, designed for the swift generation of temporal edges within distribution limits and offering a constant time complexity to generate each edge. The TED model not only accommodates diverse distribution configurations but also facilitates its seamless transfer between time-bound communities to enhance time and space efficiency. Finally, extensive experimental results demonstrate that our method outperforms baseline methods by delivering generated content of superior Quality with notably competitive time and space consumption.

Recommender systems have emerged as an indispensable mean to meet personalized interests of users and alleviate information overload. Despite the great success, accuracy-oriented recommendation models are creating information cocoons, i.e., it is becoming increasingly difficult for users to see other items they might be interested in. Although recent studies start paying attention to enhancing recommendation diversity, models based on point embedding fail to describe the range of user preferences and item features well, which is essential for diversified matching. To this end, we propose LCD-UC , a novel List-Check-Decide framework with UnCertainty masking based on box embedding to improve recommendation diversity with recommendation accuracy maintained. Specifically, LCD-UC creates hypercubes to represent users and items using box embedding for high model flexibility and expressiveness. Then, a hypercube similarity scoring function is designed to measure the similarity between hypercubes representing users and items. To make a balance between the accuracy and diversity of recommendations and achieve personalized diversity needs, we further develop a user-item pairwise attention mechanism as well as a user uncertainty masking mechanism in LCD-UC. Besides, we present two new metrics for better evaluation on recommendation diversity, which address the issue that existing metrics only consider the coverage of categories while ignore the frequency of categories. The extensive experiments on three real-world datasets show that LCD-UC can improve both recommendation accuracy and diversity over three base models, and is superior to six state-of-the-art recommendation models. An online 10-day AB test also demonstrates that LCD-UC can improve the performance of a real-world advertising system.

Subgraph matching is a common and important query for analyzing social networks. However, existing subgraph matching algorithms are still unsatisfactory in efficiency. As different subgraph matching algorithms are suitable for different conditions, this article aims to find optimization methods effective for different subgraph matching algorithms. Specifically, the contributions of this article mainly include three aspects. First, this article defines the concept of a community distribution scheme (c-scheme), and proposes an efficient generalized community-structure-aware optimization framework named GCF to accelerate the process of subgraph matching. Specifically, in the GCF framework, subgraph matching is performed by dealing with all c-schemes, and GCF can accelerate different subgraph matching algorithms by exploiting the community structure of the graph data. Second, three strategies are proposed and applied in GCF to further accelerate the process of subgraph matching. In detail, GCF analyzes the structure of the pattern graph and avoids redundant calculation with the strategy of two-level symmetry-breaking (2LS). Besides, GCF builds indexes on the community paths of the data graph to detect useless c-schemes in advance. Moreover, GCF performs community-structure-based boundary pruning and reduces the search space. Third, in the experiments, four state-of-the-art subgraph matching algorithms, i.e., TurboISO, VF3, VF3-Light, and DAF, are optimized with GCF. The results of the experiments conducted on both real-world and synthetic datasets show that the GCF is efficient and can significantly reduce the time consumption of different existing subgraph matching algorithms. Specifically, the optimized subgraph matching algorithms can be more than$2800\times $faster than the original algorithms in the best condition. Moreover, the experimental results on datasets with different scales demonstrate that GCF has considerable scalability.

Graph embedding aims to extract low-dimensional representation vectors, commonly referred to as embeddings, from graph data. The generated embeddings simplify subsequent data analysis and machine learning tasks. Recently, researchers have proposed the use of contrastive learning on graphs to extract node embeddings in an unsupervised manner. Although existing graph contrastive learning methods have significantly advanced this field, there is still potential for further exploration, particularly in optimizingtraining efficiencyand enhancingembedding quality. In this paper, we propose an efficient unsupervised graph embedding method named GEARED. First, the method involves an attributed graph reduction module that converts the raw graph into a reduced graph, greatly improving model training efficiency. Second, GEARED employs a dual-level loss with adaptive scaling factors to ensure the acquisition of high-quality embeddings. Finally, we conduct a partial derivative analysis to elucidate the specific mechanisms through which GEARED is capable of generating high-quality embeddings. Extensive experimental evaluations on 14 benchmark datasets show that GEARED consistently outperforms state-of-the-art methods in terms of training efficiency and classification accuracy. For instance, GEARED achieves a training speedup of over 40 times on both the CS and Physics datasets while maintaining superior classification accuracy.

Unsupervised graph representation learning, i.e., learning node or graph embeddings from graph data in an unsupervised manner, has become an important problem when we study graph data. With the development of self-supervised learning, researchers have designed graph-level self-supervised learning paradigms and learn embeddings under these paradigms. The learned embeddings can serve as a fine initial solution to downstream tasks such as node classification or graph classification. In this paper, we propose a fast unsupervised graph embedding method, which follows the way of self-supervised learning. This method performs representation learning on the graph under a novel concept called Graph Zoom Learning (abbr. GZL), which is orthogonal to the existing concepts of unsupervised graph embedding, such as random walk and contrastive learning. Two crucial components, graph zoom-out and point-to-point contrast, help GZL reduce the overall training time cost. Specifically, on the one hand, a lightweight miniature graph is generated from the raw graph by graph zoom-out and the learning on the miniature graph is more efficient than the learning on the raw graph; on the other hand, we design the miniature-scale learning on the miniature graph and introduce community structure into this learning pattern, which contributes to the final point-to-point contrast. Since point-to-point contrast is independent of negatives, it makes the whole training more efficient. We conduct extensive experiments to verify the advantage of GZL on representation learning. On two downstream tasks of node classification and graph classification, GZL outperforms the state-of-the-art unsupervised graph embedding methods. Particularly, on the largest experimental graph dataset (ogbn-arxiv) with 169k nodes and 1.1m edges, GZL outperforms the runner-up by 3.3% relative accuracy and achieves up to 22.6x speedup over it.

To address the variety and veracity issues of big data, data dependencies have been extended as data quality rules to adapt to various data types, ranging from (1) categorical data with equality relationships to (2) heterogeneous data with similarity relationships, and (3) numerical data with order relationships. In this survey, we briefly review the recent proposals on data dependencies categorized into the aforesaid types of data. In addition to (a) the concepts of these data dependency notations, we investigate (b) the extension relationships between data dependencies. It forms a family tree of extensions, mostly rooted in FDs. Moreover, we summarize (c) the discovery of dependencies from data, and (d) the applications of the extended data dependencies. Finally, we conclude with several directions of future studies on the emerging data.

Recommender systems are able to learn user preferences based on user and item representations via their historical behaviors. To improve representation learning, recent recommendation models start leveraging information from various behavior types exhibited by users. In real-world scenarios, the user behavioral graph is not only multiplex but also dynamic, i.e., the graph evolves rapidly over time, with various types of nodes and edges added or deleted, which causes the Neighborhood Disturbance. Nevertheless, most existing methods neglect such streaming dynamics and thus need to be retrained once the graph has significantly evolved, making them unsuitable in the online learning environment. Furthermore, the Neighborhood Disturbance existing in dynamic graphs deteriorates the performance of neighbor-aggregation based graph models. To this end, we propose SUPA, a novel graph neural network for dynamic multiplex heterogeneous graphs. Compared to neighbor-aggregation architecture, SUPA develops a sample-update-propagate architecture to alleviate neighborhood disturbance. Specifically, for each new edge, SUPA samples an influenced subgraph, updates the representations of the two interactive nodes, and propagates the interaction information to the sampled subgraph. Furthermore, to train SUPA incrementally online, we propose InsLearn, an efficient workflow for single-pass training of large dynamic graphs. Extensive experimental results on six real-world datasets show that SUPA has a good generalization ability and is superior to sixteen state-of-the-art baseline methods. The source code is available at https://github.com/shatter15/SUPA.

Graph Neural Networks (GNNs) have demonstrated promising results on exploiting node representations for many downstream tasks through supervised end-to-end training. To deal with the widespread label scarcity issue in real-world applications, Graph Contrastive Learning (GCL) is leveraged to train GNNs with limited or even no labels by maximizing the mutual information between nodes in its augmented views generated from the original graph. However, the distribution of graphs remains unconsidered in view generation, resulting in the ignorance of unseen edges in most existing literature, which is empirically shown to be able to improve GCL's performance in our experiments. To this end, we propose to incorporate graph generative adversarial networks (GANs) to learn the distribution of views for GCL, in order to i) automatically capture the characteristic of graphs for augmentations, and ii) jointly train the graph GAN model and the GCL model. Specifically, we present GACN, a novel Generative Adversarial Contrastive learning Network for graph representation learning. GACN develops a view generator and a view discriminator to generate augmented views automatically in an adversarial style. Then, GACN leverages these views to train a GNN encoder with two carefully designed self-supervised learning losses, including the graph contrastive loss and the Bayesian personalized ranking Loss. Furthermore, we design an optimization framework to train all GACN modules jointly. Extensive experiments on seven real-world datasets show that GACN is able to generate high-quality augmented views for GCL and is superior to twelve state-of-the-art baseline methods. Noticeably, our proposed GACN surprisingly discovers that the generated views in data augmentation finally conform to the well-known preferential attachment rule in online networks.

Modern recommender systems often deal with a variety of user interactions, e.g., click, forward, purchase, etc., which requires the underlying recommender engines to fully understand and leverage multi-behavior data from users. Despite recent efforts towards making use of heterogeneous data, multi-behavior recommendation still faces great challenges. Firstly, sparse target signals and noisy auxiliary interactions remain an issue. Secondly, existing methods utilizing self-supervised learning (SSL) to tackle the data sparsity neglect the serious optimization imbalance between the SSL task and the target task. Hence, we propose a Multi-Behavior Self-Supervised Learning (MBSSL) framework together with an adaptive optimization method. Specifically, we devise a behavior-aware graph neural network incorporating the self-attention mechanism to capture behavior multiplicity and dependencies. To increase the robustness to data sparsity under the target behavior and noisy interactions from auxiliary behaviors, we propose a novel self-supervised learning paradigm to conduct node self-discrimination at both inter-behavior and intra-behavior levels. In addition, we develop a customized optimization strategy through hybrid manipulation on gradients to adaptively balance the self-supervised learning task and the main supervised recommendation task. Extensive experiments on five real-world datasets demonstrate the consistent improvements obtained by MBSSL over ten state-of-the-art (SOTA) baselines. We release our model implementation at: https://github.com/Scofield666/MBSSL.git.

Recently, learning embeddings of nodes in graphs has attracted increasing research attention. There are two main kinds of graph embedding methods, i.e., transductive embedding methods and inductive embedding methods. The former focuses on directly optimizing the embedding vectors, and the latter tries to learn a mapping function for the given nodes and features. However, little work has focused on applying the learned model from one graph to another, which is a pervasive idea in Computer Vision or Natural Language Processing. Although some of the graph neural networks (GNNs) present a similar motivation, none of them considers graph biases between graphs. In this paper, we present a novel graph embedding problem called Adaptive Task (AT), and propose a unified framework for the adaptive task, which introduces two types of alignment to learn adaptive node embeddings across graphs. Then, based on the proposed framework, a novel Graph Adaptive Embedding network (GraphAE) is designed to address the adaptive task. Furthermore, we extend GraphAE to a multi-graph version to consider a more complex adaptive situation. The extensive experimental results demonstrate that our model significantly outperforms the state-of-the-art methods, and also show that our framework can make a great improvement over a number of existing GNNs.

Recently, graph neural networks have shown the superiority of modeling the complex topological structures in heterogeneous network-based recommender systems. Due to the diverse interactions among nodes and abundant semantics emerging from diverse types of nodes and edges, there is a bursting research interest in learning expressive node repre-sentations in multiplex heterogeneous networks. One of the most important tasks in recommender systems is to predict the potential connection between two nodes under a specific edge type (i.e., relationship). Although existing studies utilize explicit metapaths to aggregate neighbors, practically they only consider intra-relationship metapaths and thus fail to leverage the potential uplift by inter-relationship information. Moreover, it is not always straightforward to exploit inter-relationship metapaths comprehensively under diverse relationships, espe-cially with the increasing number of node and edge types. In addition, contributions of different relationships between two nodes are difficult to measure. To address the challenges, we propose HybridGNN, an end-to-end GNN model with hybrid aggregation flows and hierarchical attentions to fully utilize the heterogeneity in the multiplex scenarios. Specifically, HybridGNN applies a randomized inter-relationship exploration module to exploit the multiplexity property among different relationships. Then, our model leverages hybrid aggregation flows under intra-relationship metapaths and randomized exploration to learn the rich semantics. To explore the importance of different aggregation flow and take advantage of the multiplexity property, we bring forward a novel hierarchical attention module which leverages both metapath-Ievel attention and relationship-level attention. Extensive experimental results on five real-world datasets suggest that HybridGNN achieves the best performance compared to several state-of-the-art baselines (p < 0.01, t-test) with statistical significance.

Mixed data distribution is widely observed, for example, the bird migration data consist of the observed locations of various birds in different years, varying in data distribution. Learning a single regression model over such a mixed data distribution is often ineffective, while manually segmenting the data, e.g., by bird, date or region, for learning individual models is truly labor-intensive. In this paper, we propose to automatically discover the regression models that apply conditionally to only a part of the data, namely conditional regression rules (CRRs), enlightened by the conditional functional dependencies (CFDs) that are FDs hold only in some data. Remarkably, a regression model may apply in different parts of data, e.g., the seasonal migration of birds is similar in different years. To capture the shared regression models, we investigate the inference of CRRs. An algorithm is devised to learn and discover CRRs from data, with the help of CRR inference. Extensive experiments on real-world datasets demonstrate that the discovered conditional regression rules are more effective than the regression models without conditions. In particular, with the inference of CRRs, the number of learned CRRs is significantly reduced without sacrificing rule semantics.

Internet of Things (IoT) refers to an ecosystem where applications and services are driven by data collected from devices interacting with each other and the physical world. Although IoT has already brought spectacular benefits to human society, the progress is actually not as fast as expected. From network structures to control flow graphs, IoT naturally generates an unprecedented volume of graph data continuously, which stimulates fertilization and making use of advanced graph-powered methods on the diverse, dynamic, and large-scale graph IoT data.

Besides the conventional schema-oriented tasks, data dependencies are recently revisited for data quality applications, such as violation detection, data repairing and record matching. To address the variety and veracity issues of big data, data dependencies have been extended as data quality rules to adapt to various data types, ranging from (1) categorical data with equality relationships to (2) heterogeneous data with similarity relationships, and (3) numerical data with order relationships. In this survey, we briefly review the recent proposals on data dependencies categorized into the aforesaid types of data. In addition to (a) the concepts of these data dependency notations, we investigate (b) the extension relationships between data dependencies, e.g., conditional functional dependencies (CFDs) extend the conventional functional dependencies (FDs). It forms a family tree of extensions, mostly rooted in FDs, helping us understand the expressive power of various data dependencies. Moreover, we summarize (c) the discovery of dependencies from data, since data dependencies are often unlikely to be manually specified in a traditional way, given the huge volume and high variety of big data. We further outline (d) the applications of the extended data dependencies, in particular in data quality practice. It guides users to select proper data dependencies with sufficient expressive power and reasonable discovery cost. Finally, we conclude with several directions of future studies on the emerging data.

With the popularity of social networks, large-scale social graphs are necessary to evaluate the algorithms for various social network analysis tasks, especially in the era of big data. An efficient and configurable social graph generator has become more important than ever before because it is difficult to obtain billion-scale real-world social graphs for various scenarios.In this paper, we present an efficient and widely-applicable social graph generator called FastSGG. FastSGG generates social graphs according to a user-defined configuration depicting the features of the target social graph, which is a flexible way to generate graphs in a variety of applications. The generation method consists of two main steps: the determination of out-degree for a source vertex and the determination of a target vertex to construct an edge. In order to accelerate the graph generation process, a degree distribution generation (D2G) model is proposed. The D2G model is a universal model for generating graphs following different degree distributions as long as the probability density functions or probability mass functions are given. The extensive experimental results demonstrate that FastSGG can generate high-quality social graphs with small world properties, power-law degree distributions, and community structures. Moreover, FastSGG generates graphs at least four times faster than the state-of-the-art graph generators. In addition, the peak memory usage of FastSGG is less than one seventh of that of the state-of-the-art method.

Many real-world networks have been evolving, and are finely modeled as temporal graphs from the viewpoint of the graph theory. A temporal graph is informative, and always contains two types of information, i.e., the temporal information and topological information, where the temporal information reflects the time when the relationships are established, and the topological information focuses on the structure of the graph. In this paper, we perform time-topology analysis on temporal graphs to extract useful information. Firstly, a new metric named T-cohesiveness is proposed to evaluate the cohesiveness of a temporal subgraph. It defines the cohesiveness of a temporal subgraph from the time and topology dimensions jointly. Specifically, given a temporal graph G s = ( Vs , ε Es ), cohesiveness in the time dimension reflects whether the connections in G s happen in a short period of time, while cohesiveness in the topology dimension indicates whether the vertices in V s are densely connected and have few connections with vertices out of G s . Then, T-cohesiveness is utilized to perform time-topology analysis on temporal graphs, and two time-topology analysis methods are proposed. In detail, T-cohesiveness evolution tracking traces the evolution of the T-cohesiveness of a subgraph, and combo searching finds out all the subgraphs that contain the query vertex and have T-cohesiveness larger than a given threshold. Moreover, a pruning strategy is proposed to improve the efficiency of combo searching. Experimental results confirm the efficiency of the proposed time-topology analysis methods and the pruning strategy.

Network embedding, aiming to project a network into a low-dimensional space, is increasingly becoming a focus of network research. Semi-supervised network embedding takes advantage of labeled data, and has shown promising performance. However, existing semi-supervised methods would get unappealing results in thecompletely-imbalancedlabel setting where some classes have no labeled nodes at all. To alleviate this, we propose two novel semi-supervised network embedding methods. The first one is a shallow method named RSDNE. Specifically, to benefit from the completely-imbalanced labels, RSDNE guarantees both intra-class similarity and inter-class dissimilarity in an approximate way. The other method is RECT which is a new class of graph neural networks. Different from RSDNE, to benefit from the completely-imbalanced labels, RECT explores the class-semantic knowledge. This enables RECT to handle networks with node features and multi-label setting. Experimental results on several real-world datasets demonstrate the superiority of the proposed methods.

Given a network and a set of seeds related to each other, the problem of relation discovery from focusing seeds aims to discover the relations among all the seeds. Due to its wide applications, the task has been well studied in the literature. However, when facing applications where maybe not all the seeds relate to each other, methods for the task will discover many vertices unrelated to the seeds. To support such applications, a new problem called adaptive relation discovery from focusing seeds (A-RDFS) is proposed and studied in this article. Given a network and a set of seeds that may not be related to each other, discover additional vertices to reveal the relations among the seeds which are related to each other. To solve the A-RDFS problem, a relation sensitive subgraph structure called the α- relation core is proposed to find vertices related to a subset of the seeds. Thereafter, a metric called the relation quality is proposed to measure the quality of discovered relations. The metric is positively correlated with the α value of each discovered α-relation core. Hence, by maximizing the relation quality, a set of α-relation cores with large α values can be discovered, which reveals the relations among the seeds related to each other. Two algorithms are developed to optimize the relation quality. Then, using the algorithms as subroutines, the OPT-A-RDFS method is designed for the A-RDFS problem. Extensive experimental results demonstrate the performance of our methods.

Recently, learning embedding of nodes in graphs has attracted increasing research attention. There are two main kinds of graph embedding methods, i.e., the transductive embedding methods and the inductive embedding methods. The former focuses on directly optimizing the embedding vectors, and the latter tries to learn a mapping function for the given nodes and features. However, few works focus on applying the learned model from one graph to another, which is a pervasive idea in Computer Version or Natural Language Processing. Although some of the graph neural networks (GNNs) present similar motivation, none of them considers the graph bias among graphs. In this paper, we present an interesting graph embedding problem called Adaptive Task (AT), and propose a unified framework for this adaptive task, which introduces two types of alignment to learn adaptive node embedding across graphs. Then, based on the proposed framework, a novel graph adaptive embedding network is designed to address the adaptive task. Extensive experimental results demonstrate that our model significantly outperforms the state-of-the-art methods.

Recently, Graph Neural Networks (GNNs) arouse a lot of research interest and achieve great success in dealing with graph-based data. The basic idea of GNNs is to aggregate neighbor information iteratively. After k iterations, a k-layer GNN can capture nodes' k-hop local structure. In this way, a deeper GNN can access much more neighbor information leading to better performance. However, when a GNN goes deeper, the exponential expansion of neighborhoods incurs expensive computations in batched training and inference. This takes the deeper GNN away from many applications, e.g., real-time systems. In this paper, we try to learn a small GNN (called TinyGNN), which can achieve high performance and infer the node representation in a short time. However, since a small GNN cannot explore as much local structure as a deeper GNN does, there exists a neighbor information gap between the deeper GNN and the small GNN. To address this problem, we leverage peer node information to model the local structure explicitly and adopt a neighbor distillation strategy to learn local structure knowledge from a deeper GNN implicitly. Extensive experimental results demonstrate that TinyGNN is empirically effective and achieves similar or even better performance compared with the deeper GNNs. Meanwhile, TinyGNN gains a 7.73x--126.59x speed-up on inference over all data sets.

Graph embedding, also known as network embedding and network representation learning, is a useful technique which helps researchers analyze information networks through embedding a network into a low-dimensional space. However, existing graph embedding methods are all node-based, which means they can just directly map the nodes of a network to low-dimensional vectors while the edges could only be mapped to vectors indirectly. One important reason is the computational cost, because the number of edges is always far greater than the number of nodes. In this article, considering an important property of social networks, i.e., the network is sparse, and hence the average degree of nodes is bounded, we propose an edge-based graph embedding ( edge2vec ) method to map the edges in social networks directly to low-dimensional vectors. Edge2vec takes both the local and the global structure information of edges into consideration to preserve structure information of embedded edges as much as possible. To achieve this goal, edge2vec first ingeniously combines the deep autoencoder and Skip-gram model through a well-designed deep neural network. The experimental results on different datasets show edge2vec benefits from the direct mapping in preserving the structure information of edges.

As a major kind of query-dependent community detection, community search finds a densely connected subgraph containing a set of query nodes. As density is the major consideration of community search, most methods of community search often find a dense subgraph with many vertices far from the query nodes, which are not very related to the query nodes. Motivated by this, a new problem called community focusing (CF) is studied. It finds a community where the members are close and densely connected to the query nodes. A distance-sensitive dense subgraph structure called β-attention-core is proposed to remove the vertices loosely connected to or far from the query nodes, and a combinational density is designed to guarantee the density of a subgraph. Then CF is formalized as finding a subgraph with the largest combinational density among the β-attention-core subgraphs containing the query nodes with the largest β. Thereafter, effective methods are devised for CF. Furthermore, a speed-up strategy is developed to make the methods scalable to large networks. Extensive experimental results on real and synthetic networks demonstrate the performance of our methods.

Community search is an important problem in network analysis, which has attracted much attention in recent years. It starts with some given nodes, pays more attention to local network structures, and gets personalized resultant communities quickly. In this paper, we argue that there are many real scenarios where some nodes are not allowed to appear in the community. Then, we introduce a new concept called forbidden nodes and present a new problem of forbidden nodes aware community search to describe these scenarios.To address the above problem, three methods are proposed, i.e., k-core based FORTE (Forbidden nOdes awaRe communiTy sEarch), k-truss based FORTE and CW based FORTE, where the effects of both forbidden nodes and query nodes are thoroughly considered for each node in the resultant community. The former two methods are able to make use of popular community structures, while the latter is based on a new metric called weighted conductance. The extensive experiments conducted on real data sets demonstrate the effectiveness of the proposed methods.

Subgraph has gained increasing attention as it is an important query type on graphs. The efficiency of existing subgraph matching algorithms becomes unsatisfactory since graphs gradually get larger and more complex. This paper proposes an optimization method named OSMAC to accelerate subgraph matching algorithms with the community structure of data graphs. In essence, OSMAC changes the task of subgraph matching into dealing with all VC-mappings. An optimization method named community-structure-based boundary pruning is proposed to further improve the performance of OSMAC. It implements an efficient pruning method with the information of community structure and can reduce the search space. As a case study, we optimize TurboISO, one of the state-of-the-art subgraph matching algorithms, with OSMAC. The results of the experiments conducted on real-world data sets confirm that OSMAC is efficient and can improve the performance of subgraph matching algorithms significantly.

This paper presents the problem of tie direction learning which learns the directionality function of directed social networks. One way is based on hand-crafted features; the other called DeepDirect learns the social tie representation through the network topology. DeepDirect directly maps social ties to low-dimensional embedding vectors by preserving network topology, utilizing labeled data, and generating pseudo-labels based on observed directionality patterns. Experimental results on two tasks, i.e., direction discovery on undirected ties and direction quantification on bidirectional ties, demonstrate the proposed methods are effective and promising.

The problem of feature selection has attracted considerable research interest in recent years. Supervised information is capable of significantly improving the quality of selected features. However, existing supervised feature selection methods all require that classes in the labeled data (source domain) and unlabeled data (target domain) to be identical, which may be too restrictive in many cases. In this article, we consider a more challenging cross-class setting where the classes in these two domains are related but different, which has rarely been studied before. We propose a cross-class knowledge transfer feature selection framework which transfers the cross-class knowledge from the source domain to guide target domain feature selection. Specifically, high-level descriptions, i.e., attributes, are used as the bridge for knowledge transfer. To further improve the quality of the selected features, our framework jointly considers the tasks of cross-class knowledge transfer and feature selection. Experimental results on four benchmark datasets demonstrate the superiority of the proposed method.

There is a lot of research work on social ties, few of which is about the directionality of social ties. However, the directionality is actually a basic but important attribute of social ties. In this paper, we present a supervised learning problem, the tie direction learning (TDL) problem, which aims to learn the directionality function of directed social networks. Two ways are introduced to solve the TDL problem: one is based on hand-crafted features and the other, named DeepDirect, learns the social tie representation through the topological information of the network. In DeepDirect, a novel network embedding approach, which directly maps the social ties to low-dimensional embedding vectors by deep learning techniques, is proposed. DeepDirect embeds the network considering three different aspects: preserving network topology, utilizing labeled data, and generating pseudo-labels based on observed directionality patterns. Two novel applications are proposed for the learned directionality function, i.e., direction discovery on undirected ties and direction quantification on bidirectional ties. Experiments are conducted on five different real-world data sets about these two tasks. The experimental results demonstrate our methods, especially DeepDirect, are effective and promising.

Network embedding, aiming to project a network into a low-dimensional space, is increasingly becoming a focus of network research. Semi-supervised network embedding takes advantage of labeled data, and has shown promising performance. However, existing semi-supervised methods would get unappealing results in the completely-imbalanced label setting where some classes have no labeled nodes at all. To alleviate this, we propose a novel semi-supervised network embedding method, termed Relaxed Similarity and Dissimilarity Network Embedding (RSDNE). Specifically, to benefit from the completely-imbalanced labels, RSDNE guarantees both intra-class similarity and inter-class dissimilarity in an approximate way. Experimental results on several real-world datasets demonstrate the superiority of the proposed method.

The skyline of a data point set consists of the best points in the set, and is very important for multi-criteria decision making. One recent and important variant of the traditional skyline is group-based skyline, which aims to find the best groups of points in a given set. This paper brings forward an efficient approach, called minimum dominance search (MDS), to solve the g-skyline problem, a latest group-based skyline problem. MDS consists of two steps: In the first step, a novel g-skyline support structure, i.e., minimum dominance graph (MDG), is constructed to store all the points which may occur in g-skyline groups. In the second step, two searching algorithms are proposed to find g-skyline groups based on the MDG through two searching algorithms, and a skyline-combination based optimization strategy is employed to improve these two algorithms. The support for dynamic group sizes, i.e., a practical extension of the origin g-skyline problem, is provided through slightly modifying MDS. Comprehensive experiments are conducted on both synthetic and real-world data sets, and the results show that our algorithms are orders of magnitude faster than the state-of-the-art.

The skyline of a data point set is made up of the best points in the set, and is very important for multi-criteria decision making. In these years, the skyline problem attracts more and more attention, and many variants of the traditional skyline emerge in the database field. One recent and important variant is group-based skyline, which aims to find the best groups of points in a given set. In this paper, we bring forward an efficient approach, called minimum dominance search (MDS), to solve the g-skyline problem, a latest group-based skyline problem. MDS consists of two steps: In the first step, we construct a novel g-skyline support structure, i.e., minimum dominance graph (MDG), which proves to be a minimum g-skyline support structure. In the second step, we search for g-skyline groups based on the MDG through two searching algorithms, and a skyline-combination based optimization strategy is employed to improve these two algorithms. We conduct comprehensive experiments on both synthetic and real-world data sets, and show that our algorithms are orders of magnitude faster than the state-of-the-art in most cases.

Information source detection, which is the reverse problem of information diffusion, has attracted considerable research effort recently. Most existing approaches assume that the underlying propagation model is fixed and given as input, which may limit their application range. In this paper, we study the multiple source detection problem when the underlying propagation model is unknown. Our basic idea is source prominence, namely the nodes surrounded by larger proportions of infected nodes are more likely to be infection sources. As such, we propose a multiple source detection method called Label Propagation based Source Identification (LPSI). Our method lets infection status iteratively propagate in the network as labels, and finally uses local peaks of the label propagation result as source nodes. In addition, both the convergent and iterative versions of LPSI are given. Extensive experiments are conducted on several real-world datasets to demonstrate the effectiveness of the proposed method.

Most of the previous work on recommender systems focuses on discovering novel items that meet users' personalized interest. But there is barely any study about recommending repeat items that consumed by the target user before. In fact, people's consumption behaviors are a mixture of repeat and novelty-seeking behaviors [1]. Since people forget about things as time elapses, it is possible that users may prefer the previously consumed items but cannot remember them at certain times. Therefore, Recommendation for Repeat Consumption (RRC) has some real utility and should be studied in depth. Some efforts have been done in related work [1]. However, they only consider item popularity and recency effect, and fail to take full advantage of behavioral features. In this paper, we attempt to address the RRC problem (illustrated in Fig 1) by proposing a Time-Sensitive Personalized Pairwise Ranking (abbr. TS-PPR) model based on the behavioral features extracted from user implicit feedback in the consumption history. TS-PPR factorizes the temporal useritem interactions via learning the mappings from the behavioral features in observable space to the preference features in latent space, and combines users static and dynamic preferences together in recommendation. An empirical study on real-world data sets shows encouraging results.

Among the previous studies in modeling users' preference on images, most of them assume there is a consistent ranking of images, and users' preference is transitive. That is, if a user likes image A over B and B over C, it must have A over C for this user. This condition holds when user compares images from a single angle. However, if there are multiple angles to consider, users' preference may not be transitive at all. Thus, it is interesting to know whether users' pairwise preference on images can be intransitive, and how can such personalized intransitivity be modeled.

Due to the close correlation with individual's physical features and status, the adoption of cyber-physical social systems (CPSSs) has been inevitably hindered by users' privacy concerns. Such concerns keep growing as our bile devices have more embedded sensors, while the existing countermeasures only provide incapable and limited privacy preservation for sensitive physical information. Therefore, we propose a novel privacy preservation framework for CPSSs. We formulate both the privacy concerns and user expectations in CPSSs based on real-world knowledge. We also design a corresponding data publishing mechanism for users. It regulates the publishing behaviors to hide sensitive physical profiles. Meanwhile, the published data retain comprehensive social profiles for users. Our analysis demonstrates that the mechanism achieves a local maximized performance on the aspect published data size. The experiment results toward real datasets reveals that the performance is comparable to the global optimal one.

Most of the previous studies on the user preferences assume that there is a personal transitive preference ranking of the consumable media like images. For example, the transitivity of preferences is one of the most important assumptions in the recommender system research. However, the intransitive relations have also been widely observed, such as the win/loss relations in online video games, in sport matches, and even in rock-paper-scissors games. It is also found that different subjects demonstrate the personalized intransitive preferences in the pairwise comparisons between the applicants for college admission. Since the intransitivity of preferences on images has barely been studied before and has a large impact on the research of personalized image search and recommendation, it is necessary to propose a novel method to predict the personalized intransitive preferences of images. In this paper, we propose the novel Multi-Criterion preference (MuCri) models to predict the intransitive relations in the image preferences. The MuCri models utilize different kinds of image content features as well as the latent features of users and images. Meanwhile, a new data set is constructed in this paper, in order to evaluate the performance of the MuCri models. The experimental evaluation shows that the MuCri models outperform all the baselines. Due to the interdisciplinary nature of this topic, we believe it would widely attract the attention of researchers in the image processing community as well as in other communities, such as machine learning, multimedia, and recommender system.

Getting back to previously viewed web pages is a common yet uneasy task for users due to the large volume of personally accessed information on the web. This paper leverages human's natural recall process of using episodic and semantic memory cues to facilitate recall, and presents a personal web revisitation technique called WebPagePrev through context and content keywords. Underlying techniques for context and content memories' acquisition, storage, decay, and utilization for page re-finding are discussed. A relevance feedback mechanism is also involved to tailor to individual's memory strength and revisitation habits. Our 6-month user study shows that: (1) Compared with the existing web revisitation tool Memento, History List Searching method, and Search Engine method, the proposed WebPagePrev delivers the best re-finding quality in finding rate (92.10 percent), average F1-measure (0.4318), and average rank error (0.3145). (2) Our dynamic management of context and content memories including decay and reinforcement strategy can mimic users' retrieval and recall mechanism. With relevance feedback, the finding rate of WebPagePrev increases by 9.82 percent, average F1-measure increases by 47.09 percent, and average rank error decreases by 19.44 percent compared to stable memory management strategy. Among time, location, and activity context factors in WebPagePrev, activity is the best recall cue, and context+content based re-finding delivers the best performance, compared to context based re-finding and content based re-finding.

A large amount of heterogeneous event data are increasingly generated, e.g., in online systems for Web services or operational systems in enterprises. Owing to the difference between event data and traditional relational data, the matching of heterogeneous events is highly non-trivial. While event names are often opaque (e.g., merely with obscure IDs), the existing structure-based matching techniques for relational data also fail to perform owing to the poor discriminative power of dependency relationships between events. We note that interesting patterns exist in the occurrence of events, which may serve as discriminative features in event matching. In this paper, we formalize the problem of matching events with patterns. A generic pattern based matching framework is proposed, which is compatible with the existing structure based techniques. To improve the matching efficiency, we devise several bounds of matching scores for pruning. Recognizing the NP-hardness of the optimal event matching problem with patterns, we propose efficient heuristic. Finally, extensive experiments demonstrate the effectiveness of our pattern based matching compared with approaches adapted from existing techniques, and the efficiency improved by the bounding, pruning and heuristic methods.

Holistic aggregations are popular queries for users to obtain detailed summary information from Wireless Sensor Networks. An aggregation operation is holistic if there is no constant bound on the size of the storage needed to describe a sub-aggregation. Since holistic aggregation cannot be distributable, it requires that all the sensory data should be sent to the sink in order to obtain the exact holistic aggregation results, which costs lots of energy. However, in most applications, exact holistic aggregation results are not necessary; instead, approximate results are acceptable. To save energy as much as possible, we study the approximated holistic aggregation algorithms based on uniform sampling. In this article, four holistic aggregation operations, frequency, distinct-count, rank, and quantile, are investigated. The mathematical methods to construct their estimators and determine optional sample size are proposed, and the correctness of these methods are proved. Four corresponding distributed holistic algorithms to derive (ϵ, δ)-approximate aggregation results are given. The solid theoretical analysis and extensive simulation results show that all the proposed algorithms have high performance on the aspects of accuracy and energy consumption.

Community detection has attracted great interest in graph analysis and mining during the past decade, and a great number of approaches have been developed to address this problem. However, the lack of a uniform framework and a reasonable evaluation method makes it a puzzle to analyze, compare and evaluate the extensive work, let alone picking out a best one when necessary. In this paper, we design a tool called CoDAR, which reveals the generalized procedure of community detection and monitors the real-time structural changes of network during the detection process. Moreover, CoDAR adopts 12 recognized metrics and builds a rating model for performance evaluation of communities to recom- mend the best-performing algorithm. Finally, the tool also provides nice interactive windows for display.

Recommender system has been studied as a useful tool to discover novel items for users while fitting their personalized interest. Thus, the previously consumed items are usually out of consideration due to the “lack” of novelty. However, as time elapses, people may forget those previously consumed and preferred items which could become “novel” again. Meanwhile, repeat consumption accounts for a major portion of people's observed activities; examples include: eating regularly at a same restaurant, or repeatedly listening to the same songs. Therefore, we believe that recommending repeat consumption will have a real utility at certain times. In this paper, we formulate the problem of recommendation for repeat consumption with user implicit feedback. A time-sensitive personalized pairwise ranking (TS-PPR) method based on user behavioral features is proposed to address this problem. The proposed method factorizes the temporal user-item interactions via learning the mappings from the behavioral features in observable space to the preference features in latent space, and combines users' static and dynamic preferences together in recommendation. An empirical study on real-world data sets shows encouraging results.

The directionality is a significant but inherent property of social ties, though usually ignored in undirected social networks due to its invisibility. However, we believe most social ties are natively directed, and the perception of directionality can improve our understanding about the network structures and further benefit other tasks upon social networks. In this study, we address the latent tie direction inference problem in undirected social networks. We engage in the investigation of directionality on real-world large-scale directed social networks and summarize our findings using four patterns. Upon that we propose a family of ReDirect approaches, including ReDirect-N, ReDirect-T and ReDirect-One, to inferring the hidden directions of undirected social ties based on the network topology only. ReDirect can incorporate with other predictive tasks, and introduce supervision to improve performance. We also present a simple but effective strategy to construct self-labeled data. Experimental results show that even without external information, our approach can recover the directions of networks effectively. Moreover, we find the ReDirect approaches can benefit the predictive tasks remarkably in an experimental study on link prediction. The ReDirect family can be a beneficial general data preprocess tool for various network analysis tasks by uncovering the hidden directions.

Large-scale distributed computing has made available the resources necessary to solve "AI-hard" problems. As a result, it becomes feasible to automate the processing of such problems, but accuracy is not very high due to the conceptual difficulty of these problems. In this paper, we integrated crowdsourcing with MapReduce to provide a scalable innovative human-machine solution to AI-hard problems, which is called CrowdMR. In CrowdMR, the majority of problem instances are automatically processed by machine while the troublesome instances are redirected to human via crowdsourcing. The results returned from crowdsourcing are validated in the form of CAPTCHA (Completely Automated Public Turing test to Tell Computers and Humans Apart) before adding to the output. An incremental scheduling method was brought forward to combine the results from machine and human in a "pay-as-you-go" way.

Intelligent item recommendation is a key issue in AI research which enables recommender systems to be more “human-minded” when generating recommendations. However, one of the major features of human — forgetting, has barely been discussed as regards recommender systems. In this paper, we considered people’s forgetting of interest when performing personalized recommendations, and brought forward a personalized framework to integrate interest-forgetting property with Markov model. Multiple implementations of the framework were investigated and compared. The experimental evaluation showed that our methods could significantly improve the accuracy of item recommendation, which verified the importance of considering interest-forgetting in recommendations.

The short-term reconsumption behaviors, i.e. “reconsume” the near past, account for a large proportion of people’s activities every day and everywhere. In this paper, we firstly derived four generic features which influence people’s short-term reconsumption behaviors. These features were extracted with respect to different roles in the process of reconsumption behaviors, i.e. users, items and interactions. Then, we brought forward two fast algorithms with the linear and the quadratic kernels to predict whether a user will perform a short-term reconsumption at a specific time given the context. The experimental results show that our proposed algorithms are more accurate in the prediction tasks compared with the baselines. Meanwhile, the time complexity of online prediction of our algorithms is O(1), which enables fast prediction in real-world scenarios. The prediction contributes to more intelligent decision-making, e.g. potential revisited customer identification, personalized recommendation, and information re-finding.

Revealing the latent community structure, which is crucial to understanding the features of networks, is an important problem in network and graph analysis. During the last decade, many approaches have been proposed to solve this challenging problem in diverse ways, i.e. different measures or data structures. Unfortunately, experimental reports on existing techniques fell short in validity and integrity since many comparisons were not based on a unified code base or merely discussed in theory. We engage in an in-depth benchmarking study of community detection in social networks. We formulate a generalized community detection procedure and propose a procedure-oriented framework for benchmarking. This framework enables us to evaluate and compare various approaches to community detection systematically and thoroughly under identical experimental conditions. Upon that we can analyze and diagnose the inherent defect of existing approaches deeply, and further make effective improvements correspondingly. We have re-implemented ten state-of-the-art representative algorithms upon this framework and make comprehensive evaluations of multiple aspects, including the efficiency evaluation, performance evaluations, sensitivity evaluations, etc. We discuss their merits and faults in depth, and draw a set of take-away interesting conclusions. In addition, we present how we can make diagnoses for these algorithms resulting in significant improvements.

Social influence has been widely accepted to explain people's cascade behaviors and further utilized in many related applications. However, few of existing work studied the direct, microscopic and temporal impact of social influence on people's behaviors in detail. In this paper we concentrate on the behavior modeling and systematically formulate the family of behavior propagation models (BPMs) including the static models (BP and IBP), and their discrete temporal variants (DBP and DIBP). To address the temporal dynamics of behavior propagation over continuous time, we propose a continuous temporal interest-aware behavior propagation model, called CIBP. As a new member of the BPM family, CIBP exploits the continuous-temporal functions (CTFs) to model the fully-continuous dynamic variance of social influence over time. Experiments on real-world datasets evaluated the family of BPMs and demonstrated the effectiveness of our proposed approach.

In recent years, community structure has attracted increasing attention in social network analysis. However, performances of multifarious approaches to community detection are seldom evaluated in a suite of systematic measurements. Furthermore, we can hardly find works which reveal diverse features based on the detected community structure. In this paper, we build a tool called CoDEM to make both quality evaluations of community detection and an in-depth mining for pivotal nodes inside communities. This tool integrates several effective approaches to community detection, establishes an overall evaluation system and gets the multi-dimensional ranking for the local importance of nodes. Moreover, the tool is built with a friendly user interface.

Music recommendation plays a key role in our daily lives as well as in the multimedia industry. This paper adapts the memory forgetting curve to model the human interest-forgetting curve for music recommendations based on the observation of recency effects in people's listening to music. Two music recommendation methods are proposed using this model with respect to the sequence-based and the IFC-based transition probabilities, respectively. We also bring forward a learning method to approximate the global optimal or personalized interest-forgetting speed(s). The experimental results show that our methods can significantly improve the accuracy in music recommendations. Meanwhile, the IFC-based method outperforms the sequence-based method when recommendation list is short at each time.

In this demonstration, we proposed a hot plugging tool for the real-time motion-based system control, which is more portable and application-independent than the existing commercial motion-based sensing devices such as Kinect, Wii and PlayStation Move. This tool captures and recognizes people's real-time motions through the built-in camera of PCs, mobile phones or tablets, and automatically executes the system events which have been mapped with people's customized body motion, e.g., the head and the fist. The tool relieves people from the conventional ways to play games and use applications, and enables them to customize their preferred ways to control the systems.

Together with the sign (positive or negative) and strength (strong or weak), the directionality is also an important property of social ties, though usually ignored in undirected social networks for its invisibility. However, we believe most social ties are natively directed, and the awareness of directionality can improve our understanding about the network structures and further benefit social network analysis and mining tasks. Thus it's appealing to study whether there exist interesting patterns about directionality in social networks and whether we can learn the directions for undirected networks based on these patterns. In this study, we engage in the investigation of directionality patterns on real-world directed social networks and summarize our findings using four consistency hypotheses. Based on these hypotheses, we propose ReDirect, an optimization framework which makes it possible to infer the hidden directions of undirected social ties based on the network topology only. This general framework can incorporate various predictive models under specific scenarios. Furthermore, we show how to improve ReDirect by introducing semi/self-supervision in the framework and how to construct the self-labeled training data using simple but effective heuristics. Experimental results show that even without external information, our approach can recover the directions of networks effectively.

It is always attractive and challenging to explore the intricate behavior data and uncover people's motivations, preference and habits, which can greatly benefit many tasks including link prediction, item recommendation, etc. Traditional work usually studies people's behaviors without time information in a static or discrete manner, assuming the underlying factors stay invariant in a long period. However, we believe people's behaviors are dynamic, and the contributing factors including the social influence and personal preference for behaviors are varying continuously over time. Such continuous dynamics convey important knowledge about people's behavior patterns; ignoring them would lead to inaccurate models. In this work, we address the continuous dynamic modeling of temporal behaviors. To model the fully continuous temporal dynamics of behaviors and the underlying factors, we propose the DP-Space, a dynamic preference probability space, which can capture their smooth variation in various shapes over time with flexible basis functions. Upon that we propose a generative dynamic behavior model, ConTyor, which considers the temporal item-adoption behaviors as joint effect of dynamic social influence and varying personal preference over continuous time. We also develop effective inference methods for ConTyor and present its applications. We conduct a comprehensive experimental study using real-world datasets to evaluate the effectiveness of our model and the temporal modeling. Results verify that ConTyor outperforms existing state-of-the-art static and temporal models in behavior predictions. Moreover, in our detailed study on temporal modeling, we show that temporal modeling is superior to static approaches and modeling over continuous time is further better than that over discrete time. We also demonstrate that the ancient behavior data can still become important and beneficial if modeled well.

Recently, Cloud Computing is attracting great attention due to its provision of configurable computing resources. MapReduce (MR) is a popular framework for data-intensive distributed computing of batch jobs. MapReduce suffers from the following drawbacks: 1. It is sequential in its processing of Map and Reduce Phases 2. Being cluster based, its scalability is relatively limited. 3. It does not support flexible pricing. 4. It does not support stream data processing. We describe Cloud MapReduce (CMR), which overcomes these limitations. Our results show that CMR is more efficient and runs faster than other implementations of the MR framework. In addition to this, we showcase how CMR can be further enhanced to: 1. Support stream data processing in addition to batch data by parallelizing the Map and Reduce phases through a pipelining model. 2. Support flexible pricing using Amazon Cloud's spot instances and to deal with massive machine terminations caused by spot price fluctuations. 3. Improve throughput and speed-up processing over traditional MR by more than 30% for large data sets. 4. Provide added flexibility and scalability by leveraging features of the cloud computing model. Click-stream analysis, real-time multimedia processing, time-sensitive analysis and other stream processing applications can also be supported.

The study of social network evolution has attracted many attentions from both the industry and academia. In this paper we demonstrate LaFT-Explorer, a general toolkit for explaining and reproducing the network growth process based on the friendship propagation. LaFT-Explorer presents multiple perspectives for analyzing the network evolution process and structure, including LaFT-Tree, LaFT-Trace and LaFT-Flow. Upon that we build LaFT-Rec, a new visualized interactive friend recommendation service based on the friendship propagation. LaFT-Rec not only shows whom one may make friends with, but also tells the user that why you should make friends with him and how you can reach him. We demonstrate our system built upon the academic social network of DBLP.

It's well known that the transitivity of friendship is a popular sociological principle in social networks. However, it's still unknown that to what extent people's friend-making behaviors follow this principle and to what extent it can benefit the link prediction task.

Many patterns have been discovered to explain and analyze how people make friends. Among them is the triadic closure, supported by the principle of the transitivity of friendship, which means for an individual the friends of her friend are more likely to become her new friends. However, people's motivations under this principle haven't been well studied, and it's still unknown that how this principle works in diverse situations.

Music stretching resistance (MSR) is a fresh but important concept in audio signal processing, which characterizes the ability of a music piece to be stretched in time (compressed or elongated) without objectionable perceptual artifacts. It has the potential to be highly demanded in various multimedia applications like music resizing, audio editing and multimedia integration, but there is almost no prior knowledge about this property of music in literature. In this letter, the task of MSR is formulated for the first time, and an MSR classification method that employs metric learning on audio features and genres is also proposed. It attempts to automate what human acceptable time-stretching rate range of music should be. The proposed method outperforms the reference classification methods in accuracy in the comparative experiments.

SUMMARY Cloud computing has recently attracted great attention, both commercially and academically. MapReduce is a popular programming model for distributed storage and computation in the cloud. In this paper, we survey cloud‐based multimedia applications, identifying the open issues and challenges which arise when MapReduce is used for cloud computing. Copyright © 2011 John Wiley & Sons, Ltd.

SUMMARY With the rapid development of cloud computing, software applications are shifting onto cloud storage rather than remaining within local networks. Software distributions within the cloud are subject to security breaches, privacy abuses, and access control violations. In this paper, we identify an insider threat to access control which is not completely eliminated by the usual techniques of encryption, cryptographic hashes, and access‐control labels. We address this threat using software watermarking. We evaluate our access‐control scheme within the context of a Collaboration‐oriented Architecture, as defined by The Jericho Forum. Copyright © 2011 John Wiley & Sons, Ltd.

The Multi-Label Classification (MLC) problem has aroused wide concern in these years since the multi-labeled data appears in many applications, such as page categorization, tag recommendation, mining of semantic web data, social network analysis, and so forth. In this paper, we propose a novel MLC solution based on the random walk model, called MLRW. MLRW maps the multi-labeled instances to graphs, on which the random walk is applied. When an unlabeled data is fed, MLRW transforms the original multi-label problem to some single-label subproblems. Experimental results on several real-world data sets demonstrate that MLRW is a better solution to the MLC problems than many other existing multi-label classification methods.

With the rapid development of Social Network (SN for short), people increasingly pay attention to the importance of the roles which they play in the SNs. As is usually the case, the standard for measuring the importance of the members is multi-objective. The skyline operator is thus introduced to distinguish the important members from the entire community. For decision-making, people are interested in the most potential stars which can be promoted into the skyline with minimum cost, namely the problem of Member Promotion in Social Networks. In this paper, based on the characteristic of the skyline operator and the promotion process, we first of all propose some interesting new concepts such as Promotion Boundary to design a novel promotion boundary-based pruning strategy. After that, we bring forward an effective cost-based pruning strategy on the basis of permutation and combination theories to verify the plans in the ascending order of cost. The Sky Boundary algorithm is therefore proposed to solve the problem effectively by employing the optimization strategies. Extensive experiments on both real and synthetic datasets are conducted to show the application value, effectiveness and efficiency of the Sky Boundary algorithm.

Content-aware music adaption, i.e. music resizing, in temporal constraints starts drawing attention from multimedia communities because of the need of real-world scenarios, e.g. animation production and radio advertisement production. The goal of music resizing is to change the length of a music track to a user preferred length using a series of basic operations, e.g. compression, prolonging, cropping and repeating. The only existing music resizing approach so far, called LyDAR, suffers from some limitations. For example, it cannot support prolonging a music track and cannot compress music pieces with very small stretch rates. In this paper, we propose MUSIZ, a generic framework for MUsic reSIZing. Observing the diversity of quality degradation for different segments, we propose the concept of stretch-resistance to measure the degree of quality degradation after a segment is stretched. MUSIZ stretches high stretch-resistance segments intensively and relieves low stretch-resistance segments to reduce the negative impact on the stretched music piece. For short length resizing requests, we develop a contiguity-preservative cropping algorithm to remove segments before stretching, while smoothing the abrupt change at the joint between two segments. Comprehensive experimental results show that MUSIZ is superior to the existing approaches.

As 3G networks provide enhanced capabilities of data transportation, a considerable amount of mobile applications and services, which involve mass of unstructured digital content, e.g., video, audio, are available. Meanwhile, pirate and illegal distribution of these digital contents are severe issues. Digital Rights Management (DRM) aims at protecting unstructured digital contents from being abused through regulating the usage of digital contents. However, existing mobile DRM schemes more or less suffer from poor compatibility, bad practicality or high cost. Besides, to the best of our knowledge, fewer of the existent DRM schemes concern for efficient unstructured data management. In this paper, we propose Phosphor, a cloud based mobile DRM scheme with sim card. In details, an unstructured data management system is adopted for efficient data management services in DRM backend (servers and systems). Meanwhile, sim card is introduced to Phosphor, which not only reduces the cost, but also provides higher security. We have implemented our DRM scheme, which demonstrates that Phosphor is efficient, secure and practicable.

With the rapid growth of the mobile industry, a considerable amount of mobile applications and services are available. Meanwhile, pirates and illegal distributions of digital contents have become serious issues. Digital Rights Management (DRM) aims at protecting digital contents from being abused through regulating the usage of digital contents. In this paper, a cloud based SIM DRM scheme, called CS-DRM, is proposed for the mobile Internet. Also, a prototype of our DRM scheme is implemented to demonstrate the correctness, effectiveness and efficiency of CS-DRM.

In many scenarios, such as TV/radio advertising production, animation production, and presentation, music pieces are constrained in the metric of time. For example, an editor wants to use a 320s song to fit a 280s animation or to accompany a 265s radio advertisement. Current music resizing approach scales the whole piece of music in a uniform manner. However, it will degrade the effect of the compressed song and make perceptual artifacts. In this paper, a novel music resizing approach, called LyDAR (LYrics Density based Approach to non-homogeneous music Resizing), is proposed, in which the resizing operation is guided by music structural analysis. Firstly, a useful concept, lyrics density, is presented, which takes advantage of lyrics to analyze the musical structure and can be used to describe the compression-resistance for different parts of a song. Secondly, two music resizing scheduling algorithms, LDF and LDGF, are developed to schedule compression over different parts of a music piece. Finally, both subjective and objective experiments are conducted to show that LyDAR can effectively and efficiently generate compressed versions of songs with good quality.

Near duplicate detection benefits many applications, e.g., on-line news selection over the Web by keyword search. The purpose of this demo is to show the design and implementation of MapDupReducer, a MapReduce based system capable of detecting near duplicates over massive datasets efficiently.

World wide web provides plenty of multimedia resources for creating rich media web applications. However, the collected music and other media resources always mismatch in the metric of time length. Existent music resizing approaches suffer from perceptual artifacts which degrade the performance of resized music. In this paper, a novel structure-aware music resizing approach is proposed. Through lyrics analysis, our approach can compress different parts of a music piece in variant compression rates. Experimental results show that the proposed method can effectively generate resized songs with good quality.

Many activities in business process management, such as process search, process clustering, and process mining, need to determine the similarity between two process models. Although several approaches have recently been proposed to measure the behavioral similarity between business processes, all of them require that tasks in processes are properly labeled. According to these approaches, similarity between two given processes can be dramatically different under different task labeling schemes. In this paper, we consider process similarity measure from another view point, i.e., focusing on the control flow structures and ignoring the task labels. Thus, we propose a label-free similarity measure between process models based on transition adjacent relations (TARs) in the context of workflow nets (WF-nets), as well as an efficient algorithm. The experimental results involving comparison of different similarity measures on artificial processes and evaluation of the efficient algorithm on real-life processes are discussed.

Software protection and security has been a more and more important issue. In order to prevent software from unauthorized use and modification, a great many techniques have been proposed and developed. In this paper, we address this issue through a prevention technique called software watermarking, and we propose a novel software watermarking scheme, which can embed multiple non-interfering watermarks into the same program. Unlike published schemes, this scheme encodes the watermark into mapping functions and then embeds the mapping codes, which are generated from these functions, into the program at the articulation points of its control flow graph. The extraction in this scheme, which is based on dynamically loading a reconstructed program to recover the watermark, is also a novel approach to the software watermarking field. Experimental results indicate that the size and performance overheads caused by this scheme can keep steady.

A music data model, its query language and its application are proposed in this paper. Firstly, a music data model and its algebraic operations are given, which can be used to describe and manipulate musical data efficiently. Secondly, a structured query language on the model is proposed, which can be used to define and manage musical data. Finally, a digital music library, one of the applications of this model, is presented, which can be used to retrieve musical information, especially against musical instruments.