Community search is a fundamental graph-based retrieval problem that aims to identify a query-dependent subgraph whose nodes exhibit strong internal connectivity. While recent learning-based methods improve retrieval effectiveness via graph representation learning, they follow a ''one-use-one-train'' paradigm that requires retraining or fine-tuning for each target graph, leading to high data dependency, high training costs, and limited generalization. To handle this, we propose OFA-CS, a ''one-for-all'' community search framework trained once on source datasets and directly deployed to arbitrary unseen graphs without retraining or fine-tuning, while preserving strong performance. Specifically, we introduce a Spectral-Aware Feature Alignment module to unify feature dimensionality and align cross-domain semantics in a community-aware manner. We further develop a Graph Diffusion Tokenized Transformer that constructs hybrid token sequences from local and global structural contexts for Transformer encoding, and applies diffusion-based refinement to mitigate distribution shifts on unseen graphs. With the unified representations, communities are efficiently retrieved via a modularity-driven search procedure. Extensive experiments on diverse real-world graphs demonstrate that OFA-CS achieves strong cross-domain generalization and competitive retrieval effectiveness against state-of-the-art methods, without requiring target-domain supervision.

Temporal Knowledge Graph (TKG) reasoning seeks to predict future events by analyzing historical data, where the effective leverage of both local and global historical facts proves crucial. Existing approaches employ graph neural networks (GNNs) and recurrent neural networks (RNNs) for local evolution patterns, complemented by statistical methods to enhance attention to global facts, demonstrating efficient predictive capabilities. However, traditional GNNs, constrained by their low-order neighborhood aggregation design, inherently fail to model potential high-order dependencies among facts. Furthermore, existing global history modeling approaches may introduce irrelevant historical information that interferes with prediction tasks. To address these limitations, we propose a Dual History-aware HyperGraph Network for TKG reasoning, namely DHHGN. Specifically, for local history modeling, we design a hybrid hypergraph-graph joint recurrent convolution module that simultaneously captures low-order neighborhood information and high-order interaction patterns among entities, employing a gating mechanism to adaptively blend their contributions. For global history modeling, we propose a dual history enhancement module that amplifies attention on pivotal historical facts while ensuring holistic integration of all historical contexts. Extensive experiments on four public benchmarks validate that DualHist-HGN consistently outperforms existing state-of-the-art methods across TKG reasoning tasks.

ABSTRACT To celebrate the 50th Anniversary of the Information Systems Journal, we are delighted to share our research reflections on the article “Community-diversified influence maximization in social networks” published at Information Systems in 2020. Our reflections will highlight the impact of this article on the authors’ research trajectories, its influence on the broader research community, and its contributions to industry practice.

Recommender systems (RSs), as crucial components of online services, can help users efficiently obtain information they may like. In reality, RSs face long-term threats. Attackers manipulate recommendation results by injecting malicious data in order to obtain benefits. At present, research on the security of RSs lacks a comprehensive understanding of attack capabilities. Moreover, existing defense strategies have not yet been systematically associated with attack characteristics. More importantly, existing defense methods rarely focus on real unlabeled data in practical application scenarios for anomaly detection and forensics. Therefore, this survey systematically analyzes the security of RSs and provides new insights. Specifically, we first categorize attack models from an attack perspective into: attack strategies based on targets, attack strategies against security and privacy, attack strategies based on prior knowledge, and attack strategies against other RSs. From a perspective of defense, existing detection models, second, can be divided into: behavioral representation based on statistics, detection based on hidden features, detection against privacy attacks, anomaly discovery based on association mining, and abnormality forensics for real-world data. Finally, we propose several potential research directions aimed at providing guidance for the security research of RSs. Additionally, to facilitate experimental reproducibility and comparative research, this survey also provides a repository of resources for attacks and defenses (https://github.com/xiaofengbbb/RS-Papers).

Hybrid-storage blockchains have become a promising paradigm for scaling up query processing services. This paradigm provides a hybrid on/off-chain approach, where only small metadata is stored on-chain while the raw data is outsourced to off-chain storage. The key concerns for query processing in such a system are security and query integrity. However, existing schemes mostly address an impractical honest-but-curious model, rather than a more realistic malicious model, due to the intricate interplay between security and query integrity. Additionally, supporting efficient dynamic update with forward security is a significant challenge for blockchain systems. To address these issues, in this paper, we first formally define the problem of secure, reliably verifiable, and dynamic Boolean range queries in hybrid-storage blockchains (SRVF). Then, we propose a novel index called Virtual Keyword Forest (VKF), which achieves secure and reliably verifiable query processing in hybrid-storage blockchains. To support dynamic queries with forward security, we propose an adaptive version-control update scheme to integrate into VKF. Furthermore, to reduce communication overhead and gas consumption, we design an aggregation signature algorithm that ensures the verification information is of a fixed size. We provide theoretical security analysis and empirical evaluations, comparing our proposed approaches with the state-of-the-art approaches, to demonstrate their feasibility.

A corpus of recent work has revealed that authenticated query services have been under the spotlight due to the untrustworthiness of outsourced service provider. To enrich scalable functionality, there is an increasing demand for dynamically authenticated query. However, when implementing query and update simultaneously, traditional approaches heavily suffer from the inconsistency between verification digest and requested index and therefore are infeasible in reality. Moreover, the efficiency of storage, query, verification, and update is still a huge hinder when processing large scale data. To address these challenging issues, in this paper, we propose a novel idea of authenticated learned index that is carefully designed and actively optimized for authenticated query processing. Specifically, we first propose a version control update mechanism for consistency guarantee by maintaining historical index versions. Following this, we propose two basic authenticated learned indexes, i.e., query-friendly PVL-tree and update-friendly PVLB-tree, to support efficient scalable authenticated range query. Furthermore, to improve the efficiency, we introduce a hybrid index framework HPVL-tree based on two basic indexes. Extensive theoretical and experimental analysis demonstrate that our proposed HPVL-tree outperforms the state-of-the-art approaches by up to$2.28\times, 3.96\times$, and$2.51\times$in search time, update time, and verification time, respectively. Moreover, the storage overhead and communication overhead occupy only 38 % and 2.25 % of existing approach, respectively.

Representation learning technique is an effective link prediction paradigm to alleviate the incompleteness of knowledge hypergraphs. However, the n-ary complex semantic information inherent in knowledge hypergraphs causes existing methods to face the dual limitations of weak effectiveness and low efficiency. In this paper, we propose a novel knowledge hypergraph representation learning model, HySAE, which can achieve a satisfactory trade-off between effectiveness and efficiency. Concretely, HySAE builds an efficient semantic-enhanced 3D scalable end-to-end embedding architecture to sufficiently capture knowledge hypergraph n-ary complex semantic information with fewer parameters, which can significantly reduce the computational cost of the model. In particular, we also design an efficient position-aware entity role semantic embedding way and two enhanced semantic learning strategies to further improve the effectiveness and scalability of our proposed method. Extensive experimental results on all datasets demonstrate that HySAE consistently outperforms state-of-the-art baselines, with an average improvement of 9.15%, a maximum improvement of 39.44%, an average 10.39x faster, and 75.79% fewer parameters.

Knowledge graphs often suffer from incompleteness issues, which can be alleviated through information completion. However, current state-of-the-art deep knowledge convolutional embedding models rely on external convolution kernels and conventional convolution processes, which limits the feature interaction capability of the model. This paper introduces a novel dynamic convolutional embedding model, named ConvD, which directly reshapes relation embeddings into multiple internal convolution kernels. This approach effectively enhances the feature interactions between relation embeddings and entity embeddings. Simultaneously, we incorporate a priori knowledgeoptimized attention mechanism that assigns distinct contribution weights to multiple relational convolution kernels during dynamic convolution, further boosting the expressive power of the model. Extensive experiments on various datasets show that our proposed model consistently outperforms the state-of-the-art baseline methods, with average improvements ranging from 3.28% to 14.69% across all the evaluation metrics, while the number of parameters is reduced by 50.66% to 85.40% compared to other state-of-the-art models.

Session-based Recommender Systems (SBRSs) aim at timely predicting the next likely item by capturing users’ current preferences in sessions. Existing SBRSs research only focuses on maximizing session utilities, and little has been done on the fairness issue in SBRSs, which is vital but different from the same issue in traditional Recommender Systems (RSs). To fill in this gap, we define a novel concept ofsession-oriented fairnessto enforce individual items to have the same exposure accumulated within each single session, which is flexible enough to provide opportunities to achieve different fairness goals. Then, we devise a Session-Oriented Fairness-Aware algorithm (SOFA) with a dual Temporal Convolutional Networks (TCN) architecture: one is SOUP (Session-Oriented Utility Promoter) and the other is SODA (Session-Oriented Disparity Alleviator). Benefit from the collaborative learning of SOUP and SODA for the evolution of accumulated exposure in sessions,SOFAis effective to maximize session-oriented fairness while maintaining high session utilities. To the best of our knowledge, this research is the first to solve fairness issues in SBRSs. Extensive experiments on real-world datasets demonstrate thatSOFAoutperforms the state-of-the-art approaches in terms of both utility and fairness.

Knowledge hypergraph embedding models are usually computationally expensive due to the inherent complex semantic information. However, existing works mainly focus on improving the effectiveness of knowledge hypergraph embedding, making the model architecture more complex and redundant. It is desirable and challenging for knowledge hypergraph embedding to reach a trade-off between model effectiveness and efficiency. In this paper, we propose an end-to-end efficient knowledge hypergraph embedding model, HyCubE, which designs a novel3D circular convolutional neural networkand thealternate mask stackstrategy to enhance the interaction and extraction of feature information comprehensively. Furthermore, our proposed model achieves a better trade-off between effectiveness and efficiency by adaptively adjusting the 3D circular convolutional layer structure to handle$n$-ary knowledge tuples of different arities with fewer parameters. In addition, we use a knowledge hypergraph 1-N multilinear scoring way to accelerate the model training efficiency further. Finally, extensive experimental results on all datasets demonstrate that our proposed model consistently outperforms state-of-the-art baselines, with an average improvement of 8.22% and a maximum improvement of 33.82% across all metrics. Meanwhile, HyCubE is 6.12x faster, GPU memory usage is 52.67% lower, and the number of parameters is reduced by 85.21% compared with the average metric of the latest state-of-the-art baselines.

Group recommendation aims to recommend desired items for a group of users. Existing methods mainly adopt deterministic networks to represent groups as fixed-point vectors, assuming their preferences be highly close to these vectors in interest space. However, each group tends to have various interests, which cannot be fully captured by fixed-point vectors and thus calls for probabilistic modeling of interests as density instead. Although this can be supported by Variational AutoEncoder (VAE), interaction data in group recommendation are highly sparse and insufficient for VAE model training, resulting in high risks of posterior collapse and deficiency in personalization. To this end, this paper proposes a contrastive variational learning model boosted by variational model augmentation and an easyto-hard paradigm. Specifically, VAE with tailored attention is first employed to represent group preferences as variational vectors for probabilistic preference modeling. Additionally, we conduct data-agnostic augmentation via learnable variational dropout, which removes redundant or irrelevant neurons in VAE to generate meaningful augmented views adequately for contrastive learning in spite of data sparsity. Difficulty-aware negative sampling is further applied to generate high-quality negative samples adapting to varying requirements of task difficulty according to the training process. Finally, we utilize density-based variational alignment to guide the optimization process of contrastive learning. Experiments on four real-world datasets are conducted to demonstrate the significant performance improvements of our model compared with SOTA methods for group recommendation.

User engagement has recently received significant attention in understanding the decay and expansion of communities in many online social networking platforms. Many user engagement studies have been conducted to find a set of critical (anchored) users in the static social network. However, social networks are highly dynamic and their structures are continuously evolving. In this paper, we target a new research problem called Anchored Vertex Tracking (AVT), aiming to track the anchored users at each timestamp of evolving networks. To address the AVT problem, we develop a greedy algorithm inspired by the previous anchored k-core study in the static networks. Furthermore, we design an incremental algorithm to efficiently solve the AVT problem by utilizing the smoothness of the network structure's evolution. The extensive experiments demonstrate the performance of our proposed algorithms.

Blockchain has emerged as a prevailing paradigm for decentralized applications due to its reliability and transparency. To scale up retrieval services, a common strategy is to use a hybrid storage model, where on-chain storage is responsible for small metadata and off-chain storage is for outsourced raw data. However, data security and result authenticity are ongoing challenges in this scenario, and little work has been done due to the difficulty of combining result verification and privacy preservation, especially for dynamic updates while supporting forward privacy. In this paper, we formally define the problem of efficient, verifiable, and secure conjunctive keyword search in hybrid-storage blockchains (vsChain) and propose a novel hybrid index that achieves efficient query and verification while supporting dynamic updates with forward privacy guarantee. Finally, we provide empirical evaluations using real and synthetic datasets to demonstrate the feasibility of our proposed scheme.

Group recommendation aims to recommend desired items for a group of users. Due to the sparsity of group-item interactions, existing methods mainly model group preferences by aggregating member-level preference. However, they not only ignore possible user interest drift in specific groups, but also adopt deterministic models to represent group preferences using fixed-points, which are weak in characterizing uncertain group preferences. To this end, following the paradigm of variational learning, this paper proposes a multi-view attentive variational preference aggregation network called GroupAV for group rec-ommendation, so as to conduct user/group preference modeling and aggregation in a density-based manner. Specifically, we first adopt Variational AutoEncoder (VAE) to capture member-level preferences by variational vectors as density. To address user interest drift in groups, a variational preference adapter module is designed to learn group-contextualized preferences via rational transformation in variational space. Next, attentive variational aggregation networks are carefully designed for group-level preference aggregation in two different views (i.e., group-interactions and member-consensus views). Besides, we apply contrastive learning and gating fusion to optimize the multi-view learning process for the final group preference modeling of Mixture-of-Gaussian distribution. Finally, we conduct experiments on real-world datasets and demonstrate GroupAV's significant performance improvements compared to state-of-the-art group recommendation methods.

Probabilistic knowledge graphs (PKGs) improve traditional knowledge graphs by characterizing the inherent uncertainty of knowledge. In PKGs, each triple$(e_{1}, r,e_{2})$, representing that entity$e_{1}$has a relationship$r$with entity$e_{2}$, is associated with a probability$\phi$indicating its likelihood of being true. PKGs have gained popularity in various domains, such as ProBase [22] and NELL [13].

Blockchain has emerged as a prevailing paradigm for decentralized applications due to its reliability and transparency. To scale up retrieval services, a common strategy is to use a hybrid storage model, where on-chain storage is responsible for small metadata and off-chain storage is for outsourced raw data. However, data security and result authenticity are ongoing challenges in this scenario, and little work has been done due to the difficulty of combining result verification and privacy preservation, especially for dynamic updates while supporting forward privacy. In this paper, we formally define the problem of efficient, verifiable, and secure conjunctive keyword search in hybrid-storage blockchains (vsChain) and propose a novel hybrid index that achieves efficient query and verification while supporting dynamic updates with forward privacy guarantee. We also design two optimized schemes to improve query and verification performance by using a partition-based method and an obfuscated counting Bloom filter mechanism. Finally, we provide a theoretical security analysis and empirical evaluations using real and synthetic datasets to demonstrate the feasibility of our proposed schemes.

Data outsourcing to the cloud has become increasingly popular for high-speed storage and retrieval. However, privacy and security are pressing concerns that hinder the further development of cloud computing. A common approach is to encrypt data before outsourcing, assuming the cloud is semi-honest. However, in reality, the cloud may be malicious and forge query results unexpectedly. Moreover, most previous schemes are designed for single-user setting, where different users share the same secret key, leading to potential privacy leaks. Therefore, ensuring confidentiality and verifiability in multi-user setting is crucial but has not been well-addressed. In this paper, we formally define the notion of Verifiable and Secure Range Query in Multi-User Setting (VSRQM) and propose a prefix-aware encoding (Pcode) scheme to encode spatial data for query processing. Next, we design a Tree-Aided Verifiable and Secure Index (SATree) on top of the Pcode and symmetric re-encryption scheme. SATree preserves data privacy, provides a mechanism to verify query results’ integrity and achieves sub-linear search time. Additionally, we propose two compression schemes to reduce the space cost of storage and transmission. Finally, we present formal complexity and security analyses and conduct empirical evaluations on real and synthetic datasets to demonstrate our proposed approaches’ practical performance.

Searching for well-connected user communities in a Location-based Social Network (LBSN) has been extensively investigated. However, very few studies focus on finding a group of locations in an LBSN which are significantly engaged with socially cohesive user groups. In this work, we investigate the problem ofCo-engagedLocation groupSearch (CLS) from LBSNs where the selected locations are visited frequently by the members of the socially cohesive user groups, and the locations are reachable within a given distance threshold. To the best of our knowledge, this is the first work to search for socially co-engaged location groups in LBSNs. We devise a score function to measure the co-engagement of the location groups by combining social connectivity of the cohesive user groups and check-in density of the users to the selected locations. To solve theCLSproblem, we propose aFilter-and-Verifyalgorithm that effectively filters out ineligible locations, and their corresponding check-in users. Further, we derive a lower bound on the number of check-ins to prune the insignificant locations and develop a novel greedy forward expansion algorithm (GFA). To accelerate the computation ofCLS, we propose a ranking function and devise an incremental algorithm,GIA, that can filter the unqualified location groups. We establish the effectiveness of our solutions by conducting extensive experiments on three real-world datasets.

Knowledge hypergraph representation learning, which projects entities and$n$-ary relations into a low-dimensional vector space, remains a challenging area to be explored despite the ubiquity of$n$-ary relational facts in the real world. Current methods are always extensions of those used for knowledge graphs with shallow or deep structures. However, shallow and linear models limit the extraction capacity of the latent knowledge, while deep and non-linear models lead to the overabundance of parameters. In this paper, we propose a novel knowledge hypergraph completion model called HJE, which utilizes the powerful capability of convolutional neural networks for efficient representation learning. Interaction-enhanced 3D convolution and relation-aware 2D convolution are jointly utilized by HJE to extract explicit and implicit global knowledge and semantic information effectively without compromising the translation property of the model. Moreover, HJE constructs a unified learnable embedding matrix to capture entity position information in knowledge tuples. The entity mask mechanism can naturally couple the multilinear scoring approach for$n$-ary facts to speed up the training convergence of the model. Extensive experimental results on real datasets of knowledge hypergraphs and knowledge graphs demonstrate the superior performance of HJE compared with state-of-the-art baselines.

Community search over large dynamic graph has become an important research problem in modern complex networks, such as the online social network, collaboration network and biological networks. Network data in the time-varied environment has motivated several recent studies to identify the evolution of the communities. However, these studies mostly match communities of different snapshot or utilize the aggregation of the disjoint structural information and ignores the cohesion continuity. To fill this research gap, in this work, we propose a novel$(\theta ,k)$-core reliable community (CRC) and define the reliable community search problem which jointly considers member engagement, connection strength and cohesion continuity of the community in the dynamic network. We propose an online search algorithm based on eligible edge filtering and we further construct the Weighted Core Forest-Index (WCF-index) and develop efficient index-based querying algorithm with strong pruning properties. We also propose top-$l$reliable community search problem that couples query based distance to reduce the free rider effect in local community search and support flexible multiple query vertices. Extensive experiments are conducted to show the efficiency and effectiveness of the proposed algorithms.

Temporal Knowledge Graphs (TKGs), which record the evolution of relationships among entities over time, have been increasingly used in a myriad of applications. Despite their growing importance, the challenge of aligning entities in these evolving structures has yet to be satisfactorily addressed. Most existing techniques struggle to keep pace with the continual stream of new entities and relations, which is a defining characteristic of TKGs. In response to this challenge, we propose a novel teacher-student approach for incremental entity alignment in evolving TKGs. Our solution leverages a Graph Attention Network (GAT) as the teacher model and a sampling Graph Convolutional Network (GCN) as a lightweight, adaptable student model. This approach efficiently navigates the evolving complexities inherent in TKGs, leading to remarkable improvements in the efficiency and effectiveness of entity alignment. The experimental results substantiate the superior performance of our approach in achieving effective entity alignment promptly, outstripping existing state-of-the-art models. As such, our study contributes a crucial step towards efficiently handling evolving entity alignment tasks in TKGs.

Knowledge hypergraph embedding, which projects entities and n-ary relations into a low-dimensional continuous vector space to predict missing links, remains a challenging area to be explored despite the ubiquity of n-ary relational facts in the real world. Currently, knowledge hypergraph link prediction methods are essentially simple extensions of those used in knowledge graphs, where n-ary relational facts are decomposed into different subelements. Convolutional neural networks have been shown to have remarkable information extraction capabilities in previous work on knowledge graph link prediction. In this paper, we propose a novel embedding-based knowledge hypergraph link prediction model named HyConvE, which exploits the powerful learning ability of convolutional neural networks for effective link prediction. Specifically, we employ 3D convolution to capture the deep interactions of entities and relations to efficiently extract explicit and implicit knowledge in each n-ary relational fact without compromising its translation property. In addition, appropriate relation and position-aware filters are utilized sequentially to perform two-dimensional convolution operations to capture the intrinsic patterns and position information in each n-ary relation, respectively. Extensive experimental results on real datasets of knowledge hypergraphs and knowledge graphs demonstrate the superior performance of HyConvE compared with state-of-the-art baselines.

Cohesive multipartite subgraphs (CMS) in heterogeneous information networks (HINs) uncover closely connected vertex groups of multiple types, enhancing real applications like community search and anomaly detection. However, existing works for HINs pay less attention to searching CMS. In this paper, we leverage well-established concepts of meta-path and densest subgraph to propose a novel CMS model called the densest P -partite subgraph. Given a multipartite subgraph of an HIN induced by i =| P | types of vertices defined in a query meta-path P (i.e., a P -partite subgraph), we devise a novel density function which is the number of the instances of P over the geometric mean of the sizes of i different types of vertex sets in the subgraph. A P -partite subgraph with the highest density serves as the optimum result. To find the densest P -partite subgraph in an HIN with n vertices, we first design an exact algorithm with a runtime cost equivalent to solving Θ(|M|) instances of the min-cut problem where |M|= O (( n/i ) i ). Then, we attempt a more efficient approximation algorithm that achieves a ratio of 1/ i but still incurs the cost of solving Θ(|M|) instances of our proposed peeling problem. Both approaches struggle with scalability due to Θ(|M|). To overcome this bottleneck, we improve the exact algorithm with novel pruning rules that non-trivially reduce the number of min-cut problem instances to solve to O (|M|). Empirically, 70-90% instances are pruned, making the improved exact algorithm significantly faster than the approximation algorithm. Extensive experiments on real datasets demonstrate the effectiveness of the proposed model and the efficiency of our algorithms.

User engagement has recently received significant attention in understanding the decay and expansion of communities in many online social networking platforms. When a user chooses to leave a social networking platform, it may cause a cascading dropping out among her friends. In many scenarios, it would be a good idea to persuade critical users to stay active in the network and prevent such a cascade because critical users can have significant influence on user engagement of the whole network. Many user engagement studies have been conducted to find a set of critical(anchored)users in the static social network. However, social networks are highly dynamic and their structures are continuously evolving. In order to fully utilize the power of anchored users in evolving networks, existing studies have to mine multiple sets of anchored users at different times, which incurs an expensive computational cost. To better understand user engagement in evolving network, we target a new research problem calledAnchored Vertex Tracking(AVT) in this paper, aiming to track the anchored users at each timestamp of evolving networks. Nonetheless, it is nontrivial to handle the AVT problem which we have proved to be NP-hard. To address the challenge, we develop a greedy algorithm inspired by the previous anchored$k$-core study in the static networks. Furthermore, we design an incremental algorithm to efficiently solve the AVT problem by utilizing the smoothness of the network structure's evolution. The extensive experiments conducted on real and synthetic datasets demonstrate the performance of our proposed algorithms and the effectiveness in solving the AVT problem.

With the boom in cloud computing, data outsourcing in location-based services is proliferating and has attracted increasing interest from research communities and commercial applications. Nevertheless, since the cloud server is probably both untrusted and malicious, concerns about data security and result integrity have become on the rise sharply. In addition, in the single-user situation assumed by most existing works, query users can capture query content from each other even though the queries are encrypted, which may incur the leakage of query privacy. Unfortunately, there exists little work that can commendably assure data security and result integrity in the multi-user setting. To this end, in this article, we study the problem of multi-user, secure, and verifiable$k$nearest neighbor query (MSV$k$kNN). To support MSV$k$NN, we first propose a novel unified structure, called verifiable and secure index (VSI). Based on this, we devise a series of secure protocols to facilitate query processing and develop a compact verification strategy. Given an MSV$k$NN query, our proposed solution can not merely answer the query efficiently while can guarantee: 1) preservingdata privacy,query privacy,result privacy, andaccess patterns privacy; 2) authenticating thecorrectnessandcompletenessof the results; 3) supportingmulti-userwith different keys. Finally, the formal security analysis and complexity analysis are theoretically proven and the performance and feasibility of our proposed approach are empirically evaluated and demonstrated.

The development of information gathering and extraction technology has led to the popularity of multi-view data, which enables samples to be seen from numerous perspectives. Multi-view clustering (MVC), which groups data samples by leveraging complementary and consensual information from several views, is gaining popularity. Despite the rapid evolution of MVC approaches, there has yet to be a study that provides a full MVC roadmap for both stimulating technical improvements and orienting research newbies to MVC. In this article, we review recent MVC techniques with the purpose of exhibiting the concepts of popular methodologies and their advancements. This survey not only serves as a unique MVC comprehensive knowledge for researchers but also has the potential to spark new ideas in MVC research. We summarise a large variety of current MVC approaches based on two technical mechanisms: heuristic-based multi-view clustering (HMVC) and neural network-based multi-view clustering (NNMVC). We end with four technological approaches within the category of HMVC: nonnegative matrix factorisation, graph learning, latent representation learning, and tensor learning. Deep representation learning and deep graph learning are two technical methods that we demonstrate in NNMVC. We also show 15 publicly available multi-view datasets and examine how representative MVC approaches perform on them. In addition, this study identifies the potential research directions that may require further investigation in order to enhance the further development of MVC.

With the advent of location-based social networks, users can tag their daily activities in different locations through check-ins. These check-in locations signify user preferences for various socio-spatial activities and can be used to improve the quality of services in some applications such as recommendation systems, advertising, and group formation. To support such applications, in this paper, we formulate a new problem of identifying top-k Socio-Spatial co-engaged Location Selection (SSLS) for users in a social graph, that selects the best set of k locations from a large number of location candidates relating to the user and her friends. The selected locations should be (i) spatially and socially relevant to the user and her friends, and (ii) diversified both spatially and socially to maximize the coverage of friends in the socio-spatial space. To address the NP-hard and challenging problem, we first develop an exact solution by designing some pruning strategies, and also develop an approximate solution by deriving relaxed bounds and advanced termination rules. To accelerate the efficiency, we further develop a fast exact approach and a meta-heuristic approximate approach. Finally, extensive experiments are conducted to evaluate the performance of our proposed algorithms against three adapted existing methods using four real-world datasets.

Fastest route recommendation (FRR) is crucial for intelligent transportation systems. The existing methods treat it as a pathfinding problem on dynamic graphs, and extend A* algorithm with neuralized travel time estimators as cost functions. However, they fail to provide effective heuristic cost due to the neglect of its admissibility and the utilization of noise path information, resulting in sub-optimal results and inefficiency. Besides, path sequentiality is also ignored, affecting algorithm accuracy as well. In this paper, we propose a variational inference based fastest route recommendation method, which follows the framework of A* algorithm and provides effective costs for routing. Specifically, we first adopt a sequential estimator to accurately estimate the travel time of a specific path. More importantly, we design a variational inference based estimator, which models the distribution of travel time between two nodes and provides an effective heuristic cost with high probability of being admissible. We further take advantage of adversarial learning to enrich the fastest path information. To the best of our knowledge, we are the first to use variational estimator to consider the admissibility of heuristics in FRR. Extensive experiments are conducted on two real-world datasets. The results verify the performance advantage of our proposed method.

Graph Convolutional Network (GCN) has achieved extraordinary success in learning representations of nodes in graphs. However, regarding Heterogeneous Information Network (HIN), existing HIN-oriented GCN methods still suffer from two deficiencies: (1) they cannot flexibly explore all possible meta-paths and extract the most useful ones for each target object, which hinders both effectiveness and interpretability; (2) before performing aggregation, they often require some additional time-consuming pre-processing operations, which increase the computational complexity. To address the above issues, we propose an interpretable and efficient Heterogeneous Graph Convolutional Network (ie-HGCN) to learn the representations of objects in HINs. It is designed as a hierarchical aggregation architecture, i.e., object-level aggregation and type-level aggregation. The new architecture can automatically evaluate all possible meta-paths within a length limit, and discover and exploit the most useful ones for each target object, i.e., at fine granularity. It also reduces the computational cost by avoiding additional time-consuming pre-processing operations. Theoretical analysis shows its ability to evaluate the usefulness of all possible meta-paths, its connection to the spectral graph convolution on HINs, and its quasi-linear time complexity. Extensive experiments on four real network datasets demonstrate its interpretability, efficiency as well as its superiority against thirteen baselines.

In the 5 G era, data traffic has been growing rapidly. A small number of popular data files may dominate the network traffic and lead to heavy network congestion. Device-to-Device (D2D) communication can be used for caching and offloading significant data traffic. D2D social networks are instantiated paradigms of D2D communication. Existing studies maximize the performances of caching and offloading in D2D social networks by predicting potential content propagation paths. However, predicting such paths still faces many challenges, such as limitation of user spatial-temporal features, fragility of D2D social networks, and uncertainty of participants. As a solution, we first measure users' multi-dimensional features and content propagation paths to explore the distributions of D2D activities. Then we propose a D2D-LSTM model to predict complete content propagation paths hierarchically and design a prototype-user model for new participants. Experimental results demonstrate the state-of-the-art performances of D2D-LSTM. D2D-LSTM achieves at most 95% and at least 84.6% average precision in predicting terminal prototype-user class. Tree generation tests show that the generated trees have at most 64% and at least 17% similarity with ground-truth trees.

Link prediction in knowledge hypergraphs has been recognized as a critical issue in various downstream tasks for knowledge-enabled applications, from question answering to recommender systems. However, most existing approaches are primarily performed in a black-box fashion, which learn low-dimensional embeddings for inference, thus cannot provide human-understandable interpretation. In this paper, we present HyperMLN, an n-ary, mixed, and explainable framework that interprets the path-reasoning process with first-order logic, which provides a knowledge-enhanced interpretable prediction framework, in which domain knowledge in the logic rules improves the performance of embedding models, while semantic information in the embedding space can optimize the weight of the logic rules in turn. To provide benchmark rule sets for explainable link prediction methods, three types of meta-logic rules in each popular dataset are mined for interpreting results. While achieving explainability, our framework also realizes an average improvement of 3.2% on [email protected] compared to the state-of-the-art knowledge hypergraph embedding method. Our code is available at https://github.com/zirui-chen/HyperMLN.

With the popularization and application of Artificial Intelligence technology, knowledge graph embedding methods are widely used for a variety of machine learning tasks. However, most of the current knowledge graph embedding models are trained with a large number of parameters and high computational time complexity. This becomes a main obstacle to apply these existing models to large-scale knowledge graphs. To address this challenge, we propose HET-KG, a distributed system for training knowledge graph embedding efficiently. HET-KG can reduce the communication overheads by introducing a cache embedding table structure to maintain hot-embeddings at each worker. To improve the effectiveness of the cache mechanism, we design a prefetching algorithm and a filtering algorithm for adaptively selecting hot-embeddings, and provide two kinds of hot-embedding table construction strategies. To address the issue of inconsistency between the local cached hot-embeddings and the global embeddings, we also develop a hot-embedding synchronization algorithm for dynamically updating the cache embedding table, which can guarantee the inconsistency bounded within a given threshold. Finally, extensive experiments are conducted on three knowledge graph datasets FB15k, WN18, and Freebase-86m. The experimental results show that HET-KG achieves 3.7x and 1.1x speedup over the state-of-the-art systems PyTorch-BigGraph and DGL-KE, respectively.

Maximal bicliques are effective to reveal meaningful information hidden in bipartite graphs. Maximal biclique enumeration (MBE) is challenging since the number of the maximal bicliques grows exponentially w.r.t. the number of vertices in a bipartite graph in the worst case. However, a large bipartite graph is usually very sparse, which is against the worst case and may lead to fast MBE algorithms. The uncharted opportunity is taking advantage of the sparsity to substantially improve the MBE efficiency for large sparse bipartite graphs. We observe that for a large sparse bipartite graph, a vertex u may converge to a few vertices in the same vertex set as u via its neighbours, which reveals that the enumeration scope for a vertex could be very small. Based on this observation, we propose novel concepts: unilateral coreness for individual vertices, unilateral order for each vertex set and unilateral convergence (ζ) for a large sparse bipartite graph, ζ could be a few thousand for a large sparse bipartite graph with hundreds of million edges. Using the unilateral order, every vertex with τ unilateral coreness only needs to check at most 2 τ combinations so that all maximal bicliques can be enumerated and τ is bounded by ζ, which leads to a novel MBE algorithm running in O * (2 ζ ). We then propose a batch-pivots technique to eliminate all enumerations resulting in non-maximal bicliques, which guarantees that every maximal biclique is reported in O (ζ e )-delay, where e is the number of edges. We devise novel data structures that allow storing subgraphs at omissible space for further speeding up MBE. Extensive experiments are conducted on synthetic and real large datasets to justify that our proposed algorithm is faster and more scalable than the existing algorithms.

Searching for local communities is an important research problem that supports advanced data analysis in various complex networks, such as social networks, collaboration networks, cellular networks, etc. The evolution of such networks over time has motivated several recent studies to identify local communities in dynamic networks. However, these studies only utilize the aggregation of disjoint structural information to measure the quality and ignore the reliability of the communities in a continuous time interval. To fill this research gap, we propose a novel (θ, k )- core reliable community (CRC) model in the weighted dynamic networks, and define the problem of most reliable community search that couples the desirable properties of connection strength, cohesive structure continuity, and the maximal member engagement. To solve this problem, we first develop a novel edge filtering based online CRC search algorithm that can effectively filter out the trivial edge information from the networks while searching for a reliable community. Further, we propose an index structure, Weighted Core Forest-Index (WCF-index), and devise an index-based dynamic programming CRC search algorithm, that can prune a large number of insignificant intermediate results and support efficient query processing. Finally, we conduct extensive experiments systematically to demonstrate the efficiency and effectiveness of our proposed algorithms on eight real datasets under various experimental settings.

Influence maximization has recently received significant attention for scheduling online campaigns or advertisements on social network platforms. However, most studies only focus on user influence via cyber interactions while ignoring their physical interactions which are also essential to gauge influence propagation. Additionally, targeted campaigns or advertisements have not received sufficient attention. To address these issues, we first devise a novel holistic influence diffusion model that takes into account both cyber and physical user interactions in an effective and practical way. Based on the new diffusion model, we formulate a new problem ofholistic influence maximization, denoted asHIMquery, for targeted advertisements in a spatial social network. TheHIMquery problem aims to find a minimum set of users whose holistic influence can cover all target users in the network, which belongs to a set covering problem. Since theHIMquery problem is NP-hard, we develop a greedy baseline algorithm and then improve on this algorithm to reduce the computational cost. To deal with large networks, we also design a spatial-social index to maintain the social, spatial and textual information of users, as well as developing an index-based efficient solution. Finally, we conduct extensive experiments using one synthetic and three real-world datasets to validate the efficiency and effectiveness of the proposed holistic influence diffusion model and our developed algorithms.

The arrival of 5G networks has extensively promoted the growth of content delivery services (CDSs). Understanding and predicting the spatio-temporal distribution of CDSs are beneficial to mobile users, Internet Content Providers and carriers. Conventional methods for predicting the spatio-temporal distribution of CDSs are mostly base-stations (BSs) centric, leading to weak generalization and spatio coarse-grained. To improve the spatio accuracy and generalization of modeling, we propose user-centric methods for CDSs spatio-temporal analysis. With geocoding and spatio-temporal graphs modeling algorithms, CDSs records collected from mobile devices are modeled as dynamic graphs with spatio-temporal attributes. Moreover, we propose a spatio-temporal-social multi-feature extraction framework for spatio fine-grained CDSs hot spots prediction. Specifically, an edge-enhanced graph convolutional block is designed to encode CDSs information based on the social relations and the spatio dependence features. Besides, we introduce the Long Short Term Memory (LSTM) to further capture the temporal dependence. Experiments on two real-world CDSs datasets verified the effectiveness of the proposed framework, and ablation studies are taken to evaluate the importance of each feature.

Knowledge Graph (KG) representation learning aims to encode both entities and relations into a continuous low-dimensional vector space. Most existing methods only concentrate on learning representations from structural triples in Euclidean space, which cannot well exploit the rich semantic information with hierarchical structure in KGs. In this paper, we propose a novel DataType-aware hyperbolic knowledge representation learning model called DT-GCN, which has the advantage of fully embedding attribute values of data types information. We refine data types into five primitive modalities, including integer, double, Boolean, temporal, and textual. For each modality, an encoder is specifically designed to learn its embedding. In addition, we define a unified space based on Euclidean, spherical, and hyperbolic space, which is a continuous curvature space that combines advantages of three different spaces. Extensive experiments on both synthetic and real-world datasets show that our model is consistently better than the state-of-the-art models. The average performance is improved by 2.19% and 3.46% than the optimal baseline model on node classification and link prediction tasks, respectively. The results of ablation experiments demonstrate the advantages of embedding data types information and leveraging the unified space.

Session-based recommendation is to predict an anonymous user's next action based on the user's historical actions in the current session. However, the cold-start problem of limited number of actions at the beginning of an anonymous session makes it difficult to model the user's behavior, i.e., hard to capture the user's various and dynamic preferences within the session. This severely affects the accuracy of session-based recommendation. Although some existing meta-learning based approaches have alleviated the cold-start problem by borrowing preferences from other users, they are still weak in modeling the behavior of the current user. To tackle the challenge, we propose a novel cluster-based meta-learning model for session-based recommendation. Specially, we adopt a soft-clustering method and design a parameter gate to better transfer shared knowledge across similar sessions and preserve the characteristics of the session itself. Besides, we apply two self-attention blocks to capture the transition patterns of sessions in both item and feature aspects. Finally, comprehensive experiments are conducted on two real-world datasets and demonstrate the superior performance of CBML over existing approaches.

Next Point-of-Interest (POI) recommendation plays an important role in location-based services. The state-of-the-art methods utilize recurrent neural networks (RNNs) to model users' check-in sequences and have shown promising results. However, they tend to recommend POIs similar to those that the user has often visited. As a result, users become bored with obvious recommendations. To address this issue, we propose Serendipity-oriented Next POI Recommendation model (SNPR), a supervised multi-task learning problem, with objective to recommend unexpected and relevant POIs only. To this end, we define the quantitativeserendipity as a trade-off ofrelevance andunexpectedness in the context of next POI recommendation, and design a dedicated neural network with Transformer to capture complex interdependencies between POIs in user's check-in sequence. Extensive experimental results show that our model can improverelevance significantly while theunexpectedness outperforms the state-of-the-art serendipity-oriented recommendation methods.

Given a bipartite graph, the maximum balanced biclique (MBB) problem, discovering a mutually connected while disjoint sets of equal size with the maximum cardinality, plays a significant role for mining the bipartite graph and has numerous applications. Despite the NP-hardness of the MBB problem, in this paper, we show that an exact MBB can be discovered extremely fast in bipartite graphs for real applications. We propose two exact algorithms dedicated for small dense and large sparse bipartite graphs respectively. For dense bipartite graphs, an O*(1.3803n) algorithm is proposed. This algorithm in fact can find an MBB very fast for small dense bipartite graphs that are common for applications such as VLSI design. This is because, using our proposed novel techniques, the search can fast converge to sufficiently dense bipartite graphs which we prove to be polynomial-time solvable. For large sparse bipartite graphs typical for applications such as biological data analysis, an O*(1.3803 δ) algorithm is proposed, where δ is only a few hundred for large sparse bipartite graphs with millions of vertices. The indispensible optimization that leads to this time complexity is: we transform a large sparse bipartite graph into a limited number of dense subgraphs such that each of the dense subgraphs has up to δ vertices and then apply our proposed algorithm for dense bipartite graphs on each of the subgraphs. To further speed up this algorithm, tighter upper bounds, faster heuristics and more effective reductions are proposed, allowing an MBB to be discovered within a few seconds for bipartite graphs with millions of vertices. Extensive experiments are conducted on synthetic and real large bipartite graphs to demonstrate the efficiency and effectiveness of our proposed algorithms and techniques.

SimRank is a significant metric to measure the similarity of nodes in graph data analysis. The problem of SimRank computation has been studied extensively, however there is no existing work that can provide one unified algorithm to support the SimRank computation both on static and temporal graphs. In this work, we first propose CrashSim, an index-free algorithm for single-source SimRank computation in static graphs. CrashSim can provide provable approximation guarantees for the computational results in an efficient way. In addition, as the reallife graphs are often represented as temporal graphs, CrashSim enables efficient computation of SimRank in temporal graphs. We formally define two typical SimRank queries in temporal graphs, and then solve them by developing an efficient algorithm based on CrashSim, called CrashSim-T. From the extensive experimental evaluation using five real-life and synthetic datasets, it can be seen that the CrashSim algorithm and CrashSim-T algorithm substantially improve the efficiency of the state-of-the-art SimRank algorithms by about 30%, while achieving the precision of the result set with about 97%.

User engagement has recently received significant attention in understanding decay and expansion of communities in social networks. However, the problem of user engagement hasn't been fully explored in terms of users' specific interests and structural cohesiveness altogether. Therefore, we fill the gap by investigating the problem of community engagement from the perspective of attributed communities. Given a set of keywords W, a structure cohesive parameter k, and a budget parameter l, our objective is to find l number of users who can induce a maximal expanded community. Meanwhile, every community member must contain the given keywords in W and the community should meet the specified structure cohesiveness constraint k. We introduce this problem as best-Anchored Vertex set Exploration (AVE).To solve the AVE problem, we develop a Filter-Verify framework by maintaining the intermediate results using multiway tree, and probe the best anchored users in a best search way. To accelerate the efficiency, we further design a keyword-aware anchored and follower index, and also develop an index-based efficient algorithm. The proposed algorithm can greatly reduce the cost of computing anchored users and their followers. Additionally, we present two bound properties that can guarantee the correctness of our solution. Finally, we demonstrate the efficiency of our proposed algorithms and index. We measure the effectiveness of attributed community-based community engagement model by conducting extensive experiments on five real-world datasets.

With the boom in cloud computing, data outsourcing in location-based services is proliferating and has attracted increasing interest from research communities and commercial applications. Nevertheless, since the cloud server is probably both untrusted and malicious, concerns of data security and result integrity have become on the rise sharply. However, there exist little work that can commendably assure the data security and result integrity using a unified way. In this paper, we study the problem of secure and verifiable k nearest neighbor query (SVkNN). To support SVkNN, we first propose a novel unified structure, called verifiable and secure index (VSI). Based on this, we devise a series of secure protocols to facilitate query processing and develop a compact verification strategy. Given an SVkNN query, our proposed solution can not merely answer the query efficiently while can guarantee: 1) preserving the privacy of data, query, result and access patterns; 2) authenticating the correctness and completeness of the results without leaking the confidentiality. Finally, the formal security analysis and complexity analysis are theoretically proven and the performance and feasibility of our proposed approaches are empirically evaluated and demonstrated.

Geo-social group search aims to find a group of people proximate to a location while socially related. One of the driven applications for geo-social group search is organizing an impromptu activity. This is because the social cohesiveness of a found geo-social group ensures a good communication atmosphere for the activity and the spatial closeness of the geo-social group reduces the preparation time for the activity. Most existing works treat geo-social group search as a problem that finds a group satisfying a single social constraint while optimizing the spatial proximity. However, since different impromptu activities have diverse demands on attendees, e.g. an activity could require (or prefer) the attendees to have skills (or favorites) related to the activity, the existing works cannot find this kind of geo-social groups effectively. In this paper, we propose a novel geo-social group model, equipped with elegant keyword constraints, to fill this gap. We propose a novel search framework which first significantly narrows down the search space with theoretical guarantees and then efficiently finds the optimum result. To evaluate the effectiveness, we conduct experiments on real datasets, demonstrating the superiority of our proposed model. We conduct extensive experiments on large semi-synthetic datasets for justifying the efficiency of the proposed search algorithms.

Community search on attributed networks has recently attracted great deal of research interest. However, most of existing works require query users to specify some community structure parameters. This may not be always practical as sometimes a user does not have the knowledge and experience to decide the suitable parameters. In this paper, we propose a novel parameter-free contextual community model for attributed community search. The proposed model only requires a query context, i.e., a set of keywords describing the desired matching community context, while the community returned is both structure and attribute cohesive w.r.t. the provided query context. We theoretically show that both our exact and approximate contextual community search algorithms can be executed in worst case polynomial time. The exact algorithm is based on an elegant parametric maximum flow technique and the approximation algorithm that significantly improves the search efficiency is analyzed to have an approximation factor of 1/3. In the experiment, we use six real networks with ground-truth communities to evaluate the effectiveness of our contextual community model. Experimental results demonstrate that the proposed model can find near ground-truth communities. We also test both our exact and approximate algorithms using eight large real networks to demonstrate the high efficiency of the proposed algorithms.

In recent years, spatial keyword query has attracted wide-spread research attention due to the popularity of the location-based services. To efficiently support the online spatial keyword query processing, the data owners need to outsource their data and the query processing service to cloud platforms. However, the outsourcing services may raise privacy leaking issues because the cloud server on the platforms may not be trusted for both data owners and query users. Therefore, in this work, we first propose and formalize the problem of privacy-preserving boolean spatial keyword query under the widely accepted Known Background Thread Model. And then, we devise a novel privacy-preserving spatial-textual Bloom Filter encoding structure and an encrypted R-tree index. They can maintain both spatial and text information together in a secure way while answering the encrypted spatial keyword queries without the need for data decryption. To further accelerate the query processing, a compressed encrypted index is provided to deal with the challenges of the large dimension expansion and the expensive space consumption in the encrypted R-tree index. In addition, we develop the corresponding algorithms based on the designed index, and present the in-depth security analysis to show our work's satisfaction meeting the strong secure scheme. Finally, we demonstrate the performance of our proposed index and algorithms by conducting extensive experiments on four datasets under various system settings.

With the popularity of knowledge graphs growing rapidly, large amounts of RDF graphs have been released, which raises the need for addressing the challenge of distributed subgraph matching queries. In this paper, we propose an efficient distributed method to answer subgraph matching queries on big RDF graphs using MapReduce. In our method, query graphs are decomposed into a set of stars that utilize the semantic and structural information embedded RDF graphs as heuristics. Two optimization techniques are proposed to further improve the efficiency of our algorithms. One algorithm, called RDF property filtering , filters out invalid input data to reduce intermediate results; the other is to improve the query performance by postponing the Cartesian product operations. The extensive experiments on both synthetic and real-world datasets show that our method outperforms the close competitors S2X and SHARD by an order of magnitude on average.

Structural clustering is a fundamental graph mining operator which is not only able to find densely-connected clusters, but it can also identify hub vertices and outliers in the graph. Previous structural clustering algorithms are tailored to deterministic graphs. Many real-world graphs, however, are not deterministic, but are probabilistic in nature because the existence of the edge is often inferred using a variety of statistical approaches. In this paper, we formulate the problem of structural clustering on probabilistic graphs, with the aim of finding reliable clusters in a given probabilistic graph. Unlike the traditional structural clustering problem, our problem relies mainly on a novel concept called reliable structural similarity which measures the probability of the similarity between two vertices in the probabilistic graph. We develop a dynamic programming algorithm with several powerful pruning strategies to efficiently compute the reliable structural similarities. With the reliable structural similarities, we adapt an existing solution framework to calculate the structural clustering on probabilistic graphs. Comprehensive experiments on five real-life datasets demonstrate the effectiveness and efficiency of the proposed approaches.

The problem of influence maximization has recently received significant attention. However, most studies focused on user influence via cyber interactions while ignoring their physical interactions which are important to gauge influence propagation. Additionally, targeted campaigns or advertisements have not received sufficient attention. To do this, we first devise a novel holistic influence diffusion model and then formulate a new holistic influence maximization query problem and develop three algorithms. Finally, we conduct extensive experiments to evaluate the effectiveness and efficiency of the proposed solutions.

The problem of influence maximization has attracted a lot of attention as it provides a way to improve marketing, branding, and product adoption. However, existing studies rarely consider the physical locations of the social users, although location is an important factor in targeted marketing. In this paper, we investigate the problem of influence spanning maximization in location-aware social networks. Our target is to identify the maximum spanning geographical regions in a query region, which is very different from the existing methods that focus on the quantity of the activated users in the query region. Since the problem is NP-hard, we develop one greedy algorithm with a 1-1/e approximation ratio and further improve its efficiency by developing an upper bound based approach. Then, we propose the OIR index by combining ordered influential node lists and an R*-tree and design the index based solution. The efficiency and effectiveness of our proposed solutions and index have been verified using three real datasets.

We are pleased to present a special issue of Data Science and Engineering (DSE), which contains a collection of five extended papers from the DASFAA 2018 conference.Besides these five papers, this DSE issue also has one invited paper.DASFAA 2018 is the 23rd International Conference on Database Systems for Advanced Applications.DASFAA is an annual international database conference, which provides a forum for technical presentations and discussions among database researchers, developers, and users from academia, business, and industry.This year the dominant topics for the selected papers included learning models, graph and network data processing, and social network analysis, followed by text and data mining, recommendation, data quality and crowd sourcing, and trajectory and stream data.Selected papers also included topics relating to network embedding, sequence and temporal data processing, RDF and knowledge graphs, security and privacy, medical data mining, query processing and optimization, search and information retrieval, multimedia data processing, and distributed computing.The 2018 edition of DASFAA was held in Gold Coast, Australia, and attracted a total of 360 research paper submissions, spanning over numerous active and emerging topic areas.The conference program committee selected 83 full research papers and 21 short papers, six industry papers, and eight demo papers to be presented at the conference and published in the conference proceedings [1,2].The conference program also included keynote presentations by Dr.

The problem of k-truss search has been well defined and investigated to find the highly correlated user groups in social networks. But there is no previous study to consider the constraint of users' spatial information in k-truss search, denoted as co-located community search in this paper. The co-located community can serve many real applications. To search the maximum co-located communities efficiently, we first develop an efficient exact algorithm with several pruning techniques. After that, we further develop an approximation algorithm with adjustable accuracy guarantees and explore more effective pruning rules, which can reduce the computational cost significantly. To accelerate the real-time efficiency, we also devise a novel quadtree based index to support the efficient retrieval of users in a region and optimise the search regions with regards to the given query region. Finally, we verify the performance of our proposed algorithms and index using five real datasets.

A socio spatial group query finds a group of users who possess strong social connections with each other and have the minimum aggregate spatial distance to a meeting point. Existing studies limit to either finding the best group of a fixed size for a single meeting location, or a single group of a fixed size w.r.t. multiple locations. However, it is highly desirable to consider multiple locations in a real-life scenario in order to organize impromptu activities of groups of various sizes. In this paper, we propose Top k Flexible Socio Spatial Group Query (Top k-FSSGQ) to find the top k groups w.r.t. multiple POIs where each group follows the minimum social connectivity constraints. We devise a ranking function to measure the group score by combining social closeness, spatial distance, and group size, which provides the flexibility of choosing groups of different sizes under different constraints. To effectively process the Top k-FSSGQ, we first develop an Exact approach that ensures early termination of the search based on the derived upper bounds. We prove that the problem is NP-hard, hence we first present a heuristic based approximation algorithm to effectively select members in intermediate solution groups based on the social connectivity of the users. Later we design a Fast Approximate approach based on the relaxed social and spatial bounds, and connectivity constraint heuristic. Experimental studies have verified the effectiveness and efficiency of our proposed approaches on real datasets.

Social networks have become a vital mechanism to disseminate information to friends and colleagues. But the dynamic nature of information and user connectivity within these networks raised many new and challenging research problems. One of them is the query-related topic search in social networks. In this work, we investigate the important problem of the personalized influential topic search. There are two challenging questions that need to be answered: how to extract the social summarization of the social network so as to measure the topics' influence at the similar granularity scale? and how to apply the social summarization to the problem of personalized influential topic search. Based on the evaluation using real-world datasets, our proposed algorithms are proved to efficient and effective.

Detecting social communities in large social networks provides an effective way to analyze the social media users' behaviors and activities. It has drawn extensive attention from both academia and industry. One essential aspect of communities in social networks is outer influence which is the capability to spread internal information of communities to external users. Detecting the communities of high outer influence has particular interest in a wide range of applications, e.g., Ads trending analytics, social opinion mining and news propagation pattern discovery. However, the existing detection techniques largely ignore the outer influence of the communities. To fill the gap, this work investigates the Most Influential Community Search problem to disclose the communities with the highest outer influences. We firstly propose a new community model, maximal kr-Clique community, which has desirable properties, i.e., society, cohesiveness, connectivity, and maximum. Then, we design a novel tree-based index structure, denoted as C-Tree, to maintain the offline computed r-cliques. To efficiently search the most influential communities, we also develop four advanced index-based algorithms which improve the search performance of non-indexed solution by about 200 times. The efficiency and effectiveness of our solution have been extensively verified using six real datasets and a small case study.

Influence maximization is a recent but well-studied problem which helps identify a small set of users that are most likely to “influence” the maximum number of users in a social network. The problem has attracted a lot of attention as it provides a way to improve marketing, branding, and product adoption. However, existing studies rarely consider the physical locations of the users, but location is an important factor in targeted marketing. In this paper, we propose and investigate the problem of influence maximization in location-aware social networks, or, more generally,Geo-social Influence Spanning Maximization. Given a query$q$composed of a region$R$, a regional acceptance rate$\rho$, and an integer$k$as a seed selection budget, our aim is to find the maximum geographic spanning regions (MGSR). We refer to this as the MGSR problem. Our approach differs from previous work as we focus more on identifying the maximum spanning geographical regions within a region$R$, rather than just the number of activated users in the given network like the traditional influence maximization problem[14]. Our research approach can be effectively used for online marketing campaigns that depend on the physical location of social users. To address the MGSR problem, we first prove NP-Hardness. Next, we present a greedy algorithm with a$1-1/e$approximation ratio to solve the problem, and further improve the efficiency by developing an upper bounded pruning approach. Then, we propose the OIR*-Tree index, which is a hybrid index combining ordered influential node lists with an R*-tree. We show that our index based approach is significantly more efficient than the greedy algorithm and the upper bounded pruning algorithm, especially when$k$is large. Finally, we evaluate the performance for all of the proposed approaches using three real datasets.

Recently, answering keyword queries on graph data has drawn a great deal of attention from database communities. However, most graph keyword search solutions proposed so far primarily focus on a single query setting. We observe that for a popular keyword query system, the number of keyword queries received could be substantially large even in a short time interval, and the chance that these queries share common keywords is quite high. Therefore, answering keyword queries in batches would significantly enhance the performance of the system. Motivated by this, this paper studies efficient batch processing for multiple keyword queries on graph data. Realized that finding both the optimal query plan for multiple queries and the optimal query plan for a single keyword query on graph data are computationally hard, we first propose two heuristic approaches which target maximizing keyword overlap and give preferences for processing keywords with short sizes. Then we devise a cardinality based cost estimation model that takes both graph data statistics and search semantics into account. Based on the model, we design an A* based algorithm to find the global optimal execution plan for multiple queries. We evaluate the proposed model and algorithms on two real datasets and the experimental results demonstrate their efficacy.

Graph data management and matching similar graphs are very important for many applications including bioinformatics, computer vision, VLSI design, bug localization, road networks, social and communication networking. Many graph indexing and similarity matching techniques have already been proposed for managing and querying graph data. In similar graph matching, a user is returned with the database graphs whose distances with the query graph are below a threshold. In such query settings, a user may not receive certain database graphs that are very similar to the query graph if the initial query graph is inappropriate/imperfect for the expected answer set. To exemplify this, consider a drug designer who is looking for chemical compounds that could be the target of her hypothetical drug before realizing it. In response to her query, the traditional search system may return the structures from the database that are most similar to the query graph. However, she may get surprised if some of the expected targets are missing in the answer set. She may then seek assistance from the system by asking “Is there other query graph that can match my expected answer set?”. The system may then modify her initial query graph to include the missing answers in the new answer set. Here, we study this kind of problem of answering why-not questions in similar graph matching for graph databases.

It has been estimated that the cumulative sales of Electric Vehicles (EVs) will be up to 5.9 million and the stock of EVs will be up to 20 million by 2020 [1]. As the number of EVs is expanding, there is a growing need for widely distributed, publicly accessible, EV charging facilities. The public EV Chargers (EVCs) are expected to be found and will be needed where there is on-street parking, at taxi stands, in parking lots at places of employment, hotels, airports, shopping centres, convenience shops, fast food restaurants, and coffee houses, etc. In this work, we aim to optimize the distribution of public EVCs across the city such that (i) the overall revenue generated by the EVCs is maximized, subject to (ii) the overall driver discomfort (e.g., queueing time) for EV charging is minimized. This is the first study on EVC distribution where EVCs are assumed to be installed in almost all regions across a city. The problem is formulated using a bilevel optimization model. We propose an alternating framework to solve it and have proved that a local minima is achievable. Moreover, this work introduces novel methods to extract information to understand the discomfort of petroleum car drivers, EV charging demands, parking time and parking fees across the city. The source data explored include the trajectories of taxis, the distribution of petroleum stations and various local features. The empirical study uses the real data sets from Shenzhen City, one of the largest cities in China. The extensive tests verify the superiority of the proposed bilevel optimization model in all aspects.

The study of urban networks reveals that the accessibility of important city objects for the vehicle traffic and pedestrians is significantly correlated to the popularity, micro-criminality, micro-economic vitality, and social liveability of the city, and is always the chief factor in regulating the growth and expansion of the city. The accessibility between different components of an urban structure are frequently measured along the streets and routes considered as edges of a planar graph, while the traffic ultimate destination points and street junctions are treated as vertices. For estimation of the accessibility of destination vertex$j$from vertex$i$through urban networks, in particular, the random walks are used to calculate the expected distance a random walker starting from$i$makes before$j$is visited (known asaccess time). The state-of-the-art of access time computation is costly in large planar graphs since it involves matrix operation over entire graph. The time complexity is$O(n^{2.376})$where$n$is the number of vertices in the planar graph. To enable efficient access time query answering in large planar graphs, this work proposes the first access time oracle which is based on the proposed access time decomposition and reconstruction scheme. The oracle is a hierarchical data structure with deliberate design on the relationships between different hierarchical levels. The storage requirement of the proposed oracle is$O(n^{\frac{4}{3}}\log \log n)$and the access time query response time is$O(n^{\frac{2}{3}})$. The extensive tests on a number of large real-world road networks (with up to about 2 million vertices) have verified the superiority of the proposed oracle.

Social networks are a vital mechanism to disseminate information to friends and colleagues. In this work, we investigate an important problem—thepersonalized influential topic search, or PIT-Search in a social network: Given a keyword query$q$issued by a user$u$in a social network, a PIT-Search is to find the top-$k$$q$-related topics that are most influential for the query user$u$. The influence of a topic to a query user depends on the social connection between the query user and the social users containing the topic in the social network. To measure the topics’ influence at the similar granularity scale, we need to extract the social summarization of the social network regarding topics. To make effective topic-aware social summarization, we propose two random-walk based approaches: random clustering and an L-length random walk. Based on the proposed approaches, we can find a small set of representative users with assigned influential scores to simulate the influence of the large number of topic users in the social network with regards to the topic. The selected representative users are denoted as the social summarization of topic-aware influence spread over the social network. And then, we verify the usefulness of the social summarization by applying it to the problem of personalized influential topic search. Finally, we evaluate the performance of our algorithms using real-world datasets, and show the approach is efficient and effective in practice.

Answeringwhy-notquestions in databases is promised to have wide application prospect in many areas and thereby, has attracted recent attention in the database research community. This paper addresses the problem of answering these so-calledwhy-notquestions in similar graph matching for graph databases. Given a set of answer graphs of an initial query graph$q$and a set of missing (why-not) graphs, we aim to modify$q$into a new query graph$q^*$such that the missing graphs are included in the new answer set of$q^*$. We present an approximate solution to address the above as the optimal solution is NP-hard to compute. In our approach, we first compute the bounded search space and the distance to be minimized for$q^*$. Then, we present a two-phase algorithm to find the new query$q^*$. In the first phase, we generate a set of candidate edges to be added/deleted into/from the initial query$q$within the bounded search space and in the second phase, we select a subset of candidate edges generated in the first phase to minimize the distance for$q^*$. We also demonstrate the effectiveness and efficiency of our approach by conducting extensive experiments on two real datasets.

While keyword query empowers ordinary users to search vast amount of data, the ambiguity of keyword query makes it difficult to effectively answer keyword queries, especially for short and vague keyword queries. To address this challenging problem, in this paper we propose an approach that automatically diversifies XML keyword search based on its different contexts in the XML data. Given a short and vague keyword query and XML data to be searched, we first derive keyword search candidates of the query by a simple feature selection model. And then, we design an effective XML keyword search diversification model to measure the quality of each candidate. After that, two efficient algorithms are proposed to incrementally compute top-k qualified query candidates as the diversified search intentions. Two selection criteria are targeted: the k selected query candidates are most relevant to the given query while they have to cover maximal number of distinct results. At last, a comprehensive evaluation on real and synthetic data sets demonstrates the effectiveness of our proposed diversification model and the efficiency of our algorithms.

Recent years have witnessed an unprecedented proliferation of social media, e.g., millions of blog posts, micro-blog posts, and social networks on the Internet. This kind of social media data can be modeled in a large graph where nodes represent the entities and edges represent relationships between entities of the social media. Discovering keyword-based correlated networks of these large graphs is an important primitive in data analysis, from which users can pay more attention about their concerned information in the large graph. In this paper, we propose and define the problem of keyword-based correlated network computation over a massive graph. To do this, we first present a novel tree data structure that only maintains the shortest path of any two graph nodes, by which the massive graph can be equivalently transformed into a tree data structure for addressing our proposed problem. After that, we design efficient algorithms to build the transformed tree data structure from a graph offline and compute the γ-bounded keyword matched subgraphs based on the pre-built tree data structure on the fly. To further improve the efficiency, we propose weighted shingle-based approximation approaches to measure the correlation among a large number of γ-bounded keyword matched subgraphs. At last, we develop a merge-sort based approach to efficiently generate the correlated networks. Our extensive experiments demonstrate the efficiency of our algorithms on reducing time and space cost. The experimental results also justify the effectiveness of our method in discovering correlated networks from three real datasets.

The probabilistic threshold query is one of the most common queries in uncertain databases, where a result satisfying the query must be also with probability meeting the threshold requirement. In this paper, we investigate probabilistic threshold keyword queries (PrTKQ)over XML data, which is not studied before. We first introduce the notion of quasi-SLCA and use it to represent results for a PrTKQ with the consideration of possible world semantics. Then we design a probabilistic inverted (PI)index that can be used to quickly return the qualified answers and filter out the unqualified ones based on our proposed lower/upper bounds. After that, we propose two efficient and comparable algorithms: Baseline Algorithm and PI index-based Algorithm. To accelerate the performance of algorithms, we also utilize probability density function. An empirical study using real and synthetic data sets has verified the effectiveness and the efficiency of our approaches.

In this paper, we study how to find maximal k-edge-connected subgraphs from a large graph. k-edge-connected subgraphs can be used to capture closely related vertices, and finding such vertex clusters is interesting in many applications, e. g., social network analysis, bioinformatics, web link research. Compared with other explicit structures for modeling vertex clusters, such as quasi-clique, k-core, which only set the requirement on vertex degrees, k-edge-connected subgraph further requires high connectivity within a subgraph (a stronger requirement), and hence defines a more closely related vertex cluster.

Despite the proliferation of work on XML keyword query, it remains open to support keyword query over probabilistic XML data. Compared with traditional keyword search, it is far more expensive to answer a keyword query over probabilistic XML data due to the consideration of possible world semantics. In this paper, we firstly define the new problem of studying top-k keyword search over probabilistic XML data, which is to retrieve k SLCA results with the k highest probabilities of existence. And then we propose two efficient algorithms. The first algorithm PrStack can find k SLCA results with the k highest probabilities by scanning the relevant keyword nodes only once. To further improve the efficiency, we propose a second algorithm EagerTopK based on a set of pruning properties which can quickly prune unsatisfied SLCA candidates. Finally, we implement the two algorithms and compare their performance with analysis of extensive experimental results.

An important facility to aid keyword search on XML data is suggesting alternative queries when user queries contain typographical errors. Query suggestion thus can improve users' search experience by avoiding returning empty result or results of poor qualities. In this paper, we study the problem of effectively and efficiently providing quality query suggestions for keyword queries on an XML document. We illustrate certain biases in previous work and propose a principled and general framework, XClean, based on the state-of-the-art language model. Compared with previous methods, XClean can accommodate different error models and XML keyword query semantics without losing rigor. Algorithms have been developed that compute the top-k suggestions efficiently. We performed an extensive experiment study using two large-scale real datasets. The experiment results demonstrate the effectiveness and efficiency of the proposed methods.

Although keyword query enables inexperienced users to easily search XML database with no specific knowledge of complex structured query languages or XML data schemas, the ambiguity of keyword query may result in generating a great number of results that may be classified into different types. For users, each result type implies a possible search intention. To improve the performance of keyword query, it is desirable to efficiently work out the most relevant result type from the data to be retrieved.

Keyword search is integrated in many applications on account of the convenience to convey users' query intention. Recently, answering keyword queries on XML data has drawn the attention of web and database communities, because the success of this research will relieve users from learning complex XML query languages, such as XPath/XQuery, and/or knowing the underlying schema of the queried XML data. As a result, information in XML data can be discovered much easier.