Automatic playlist continuation (APC) is now essential in music streaming platforms that enable users to discover new music tracks and artists with a seamless interface. To achieve attractive user experiences, it is vital to recommend music tracks that meet the users' interests. However, it is difficult for existing recommendation methods to find effective tracks since the platform includes massive music tracks associated with complex property relationships. In this paper, we propose a novel recommendation algorithm for effective APC. To improve the recommendation accuracy, our algorithm excludes unpromising properties by using a biased graph-based search method. Our extensive experiments on real-world playlists clarify that our algorithm outperforms the state-of-the-art methods in terms of recommendation accuracy.

The Maximum k-Plex Search (MPS) can find the largest k-plex, which is a generalization of the largest clique. Although MPS is commonly used in AI to effectively discover real-world communities of social networks, existing MPS algorithms suffer from high computational costs because they iteratively scan numerous nodes to find the largest k-plex. Here, we present an efficient MPS algorithm called Branch-and-Merge (BnM), which outputs an exact maximum k-plex. BnM merges unnecessary nodes to explore a smaller graph than the original one. Extensive evaluations on real-world social networks demonstrate that BnM significantly outperforms other state-of-the-art MPS algorithms in terms of running time.

Affinity Propagation (AP) is a fundamental algorithm to identify clusters included in data objects. Given a similarities among objects, it iteratively performs message updates between all data object pairs until convergence. Although AP yields a higher clustering quality compared with other methods, it is computationally expensive. Hence, it has difficulty handling massive datasets that include numerous data objects. This is because the message updates require a quadratic cost of the number of data objects. Here, we propose a novel fast algorithm, ScaleAP, which outputs the same clusters as AP but within a shorter computation time. ScaleAP dynamically excludes unnecessary message updates without sacrificing its clustering accuracy. Our extensive evaluations demonstrate that ScaleAP outperforms existing AP algorithms in terms of running time by up to two orders of magnitude.

k nearest neighbor (kNN) query is an essential graph data management tool to find relevant data entities suited to a user-specified query node. Graph indexing methods have the potential to achieve a quick kNN search response, the graph indexing methods are one of the promising approaches. However, they struggle to handle large-scale complex networks since constructing indexes and to querying kNN nodes in the large-scale networks are computationally expensive. In this paper, we propose a novel graph indexing algorithm for a fast kNN query on large networks. To overcome the aforementioned limitations, our algorithm generates two types of indexes based on the topological properties of complex networks. Our extensive experiments on real-world graphs clarify that our algorithm achieves up to 18,074 times faster indexing and 146 times faster kNN query than the state-of-the-art methods.

How can the most appropriate community be found given an attributed graph and a user-specified query node? The community search algorithm is currently an essential graph data management tool to find a community suited to a user-specified query node. Although community search algorithms are useful in various web-based applications and services, they have trouble handling attributed graphs due to the strict topological constraints of traditional algorithms. In this paper, we propose an accurate community search algorithm for attributed graphs. To overcome current limitations, we define a new attribute-driven community search problem class called the Flexible Attributed Truss Community (F-ATC). The advantage of the F-ATC problem is that it relaxes topological constraints, allowing diverse communities to be explored. Consequently, the community search accuracy is enhanced compared to traditional community search algorithms. Additionally, we present a novel heuristic algorithm to solve the F-ATC problem. This effective algorithm detects more accurate communities from attributed graphs than the traditional algorithms. Finally, extensive experiments are conducted using real-world attributed graphs to demonstrate that our approach achieves a higher accuracy than the state-of-the-art method.

Given a bi-type information network, which is an extended model of well-known bipartite graphs, how can clusters be efficiently found in graphs? Graph clustering is now a fundamental tool to understand overviews from graph-structured data. The RankClus framework accurately performs clustering for bi-type information networks using ranking-based graph clustering techniques. It integrates a graph ranking algorithms such as PageRank or HITS into graph clustering procedures to improve the clustering quality. However, this integration incurs a high computational cost to handle large bi-type information networks since RankClus repeatedly computes the ranking algorithm for all nodes and edges until the clustering procedure converges. To overcome this runtime limitation, herein we present a novel RankClus algorithm that reduces the running time for large bi-type information networks. Our proposed method employs dynamic graph processing techniques into the ranking procedures included in RankClus. By dynamically updating ranking results, our proposal reduces the number of computed nodes and edges during repeated ranking procedures. We experimentally verify using real-world datasets that our proposed method successfully reduces the running time while maintaining the clustering quality of RankClus.

Modularity clustering is an essential tool to understand complicated graphs. However, existing methods are not applicable to massive graphs due to two serious weaknesses. (1) It is difficult to fully reproduce ground-truth clusters due to the resolution limit problem. (2) They are computationally expensive because all nodes and edges must be computed iteratively. This paper proposes gScarf, which outputs fine-grained clusters within a short running time. To overcome the aforementioned weaknesses, gScarf dynamically prunes unnecessary nodes and edges, ensuring that it captures fine-grained clusters. Experiments show that gScarf outperforms existing methods in terms of running time while finding clusters with high accuracy.

Affinity Propagation is one of the fundamental clustering algorithms used in various Web-based systems and applications. Although Affinity Propagation can find highly accurate clusters, it is computationally expensive to apply Affinity Propagation to a large dataset since it requires to iteratively compute all possible pairs of data objects in the dataset. In this paper, we propose a novel Affinity Propagation algorithm named C-AP for tackling this problem. Towards the problem, C-AP employs cell-based index to reduce the number of the computed pairs in the clustering procedure. By using the cell-based index, C-AP efficiently detects unnecessary pairs, which do not contribute to its clustering result. As a result, C-AP detects the same clusters as those of Affinity Propagation with much shorter computation time. Extensive evaluations demonstrate the performance superiority of C-AP over the state-of-the-art algorithms.

Graph clustering is one of the key techniques for understanding structures present in the complex graphs such as Web pages, social networks, and others. In the Web and data mining communities, modularity-based graph clustering algorithm is successfully used in many applications. However, it is difficult for the modularity-based methods to find fine-grained clusters hidden in large-scale graphs; the methods fail to reproduce the ground truth. In this paper, we present a novel modularity-based algorithm, CAV-Partitioning, that shows better clustering results than the traditional algorithm. In our proposed method, we introduce cohesiveness-aware vector partitioning into the graph spectral analysis to improve the clustering accuracy. Extensive experiments on public datasets demonstrate the performance superiority of CAV-Partitioning over the state-of-the-art approaches.

The demands for graph data analysis methods, e.g., clustering and ranking, are increasing. RankClus is a framework to extract good clusters by integrating clustering and ranking on heterogeneous graphs; it enhances the clustering results by alternately updates the results of clustering and ranking for the better understanding of the clusters. However, RankClus is computationally expensive if a graph is large since it needs to iterate both clustering and ranking for all nodes. In this paper, to address this problem, we propose a novel fast RankClus algorithm for heterogeneous graphs. To speed up the entire procedure of RankClus, our proposed algorithm reduces the computational cost of the ranking process in each iteration. Our proposal measures how each node affects the clustering result; if it is not significant, we prune the node. Our extensive evaluations showed that our proposal is much faster than the original method.

Given brain and myoelectric signals taken from a mouse, how can we classify its sleep stages accurately? Classifying sleep stages is the fundamental problem in recent diagnoses and clinical researches. However, sleep staging suffers from a serious weakness, clinical experts visually inspect the brain and myoelectric signals to improve sleep staging accuracy. This is because recent diagnoses and clinical researches require classification accuracy at least 95% so as to enhance preciseness of their analyses. In this paper, we present an automatic classification method MASC based on the following three approaches: (1) it extracts effective features for fully representing each sleep stage property, (2) it classifies sleep stages by using temporal patterns of sleep stage transitions, and (3) it re-classifies sleep stages only for the results with low-confidence. As a result, MASC achieves more than 95% accuracy for both noisy and noiseless mice data.

Maintaining infrastructures (e.g., roadway) is a critical issue for local governments. Data from physical devices and reports from citizens through social networks are helpful to observe conditions of infrastructures. This paper proposes a framework called SOLA for integrating and analysing data from multiple sources including streaming data and static data for roadway management. The framework integrates data from multiple sources in the way of stream OLAP architecture, and analyses the integrated data in terms of OLAP analysis. This paper applies the framework to support roadway managements of local governments, and develops the application called SOLAR. SOLAR aims at providing historical views of roadway patrols as well as roadway statuses for assisting in determining roadway patrolling schedules. The real-world use case on a city exhibits the applicability of SOLAR with positive feedbacks from city officers. SOLA is a promising framework for big data analysis and smart city applications, as the number, amount, and speed of generating data increase in the era of big data and smart city.

There is a large demand for distributed engines that efficiently process large-scale graph data, such as social graph and web graph. The distributed graph engines execute analysis process after partitioning input graph data and assign them to distributed computers, so the quality of graph partitioning largely affects the communication cost and load balance among computers during the analysis process. We propose an effective graph partitioning technique that achieves low communication cost and good load balance among computers at the same time. We first generate more clusters than the number of computers by extending the modularity-based clustering, and then merge those clusters into balanced-size clusters until the number of clusters becomes the number of computers by using techniques designed for graph packing problem. We implemented our technique on top of distributed graph engine, PowerGraph, and made intensive experiments. The results show that our partitioning technique reduces the communication cost so it improves the response time of graph analysis patterns. In particular, PageRank computation is 3.2 times faster at most than HDRF, the state-of-the art of streaming-based partitioning approach.

For the AI community, the lasso proposed by Tibshirani is an important regression approach in finding explanatory predictors in high dimensional data. The coordinate descent algorithm is a standard approach to solve the lasso which iteratively updates weights of predictors in a round-robin style until convergence. However, it has high computation cost. This paper proposes Sling, a fast approach to the lasso. It achieves high efficiency by skipping unnecessary updates for the predictors whose weight is zero in the iterations. Sling can obtain high prediction accuracy with fewer predictors than the standard approach. Experiments show that Sling can enhance the efficiency and the effectiveness of the lasso.

Ahead-of-time data layout optimization by vertex reordering is a widely used technique to improve memory access locality in graph analysis. While reordered graphs yield better analysis performance, the existing reordering algorithms use significant amounts of computation time to provide efficient vertex ordering, hence, they fail to reduce end-to-end processing time. This paper presents a first algorithm for just-in-time parallel reordering, named Rabbit Order. It reduces end-to-end runtime by achieving high locality and fast reordering at the same time through two approaches. The first approach is hierarchical community-based ordering, which exploits the locality derived from hierarchical community structures in real-world graphs. Our ordering fully leverages low-latency cache levels by mapping hierarchical communities into hierarchical caches. The second approach is parallel incremental aggregation, which improves the runtime efficiency of reordering by decreasing the number of vertices to be processed. In addition, this approach utilizes lightweight atomic operations for concurrency control to avoid locking overheads and achieve high scalability. Our experiments show that Rabbit Order significantly outperforms state-of-the-art reordering algorithms.

Affinity Propagation is a clustering algorithm used in many applications. It iteratively updates messages between data points until convergence. The message updating process enables Affinity Propagation to have higher clustering quality compared with other approaches. However, its computation cost is high; it is quadratic in the number of data points. This is because it updates the messages of all data point pairs. This paper proposes an efficient algorithm that guarantees the same clustering results as the original algorithm. Our approach, F-AP, is based on two ideas: (1) it computes upper and lower estimates to limit the messages to be updated in each iteration, and (2) it dynamically detects converged messages to efficiently skip unneeded updates. Experiments show that F-AP is much faster than previous approaches with no loss in clustering performance.

Graph clustering is one of the key techniques for understanding the structures present in graphs. Besides cluster detection, identifying hubs and outliers is also a key task, since they have important roles to play in graph data mining. The structural clustering algorithm SCAN , proposed by Xu et al. , is successfully used in many application because it not only detects densely connected nodes as clusters but also identifies sparsely connected nodes as hubs or outliers. However, it is difficult to apply SCAN to large-scale graphs due to its high time complexity. This is because it evaluates the density for all adjacent nodes included in the given graphs. In this paper, we propose a novel graph clustering algorithm named SCAN ++. In order to reduce time complexity, we introduce new data structure of directly two-hop-away reachable node set (DTAR). DTAR is the set of two-hop-away nodes from a given node that are likely to be in the same cluster as the given node. SCAN++ employs two approaches for efficient clustering by using DTARs without sacrificing clustering quality. First, it reduces the number of the density evaluations by computing the density only for the adjacent nodes such as indicated by DTARs. Second, by sharing a part of the density evaluations for DTARs, it offers efficient density evaluations of adjacent nodes. As a result, SCAN++ detects exactly the same clusters, hubs, and outliers from large-scale graphs as SCAN with much shorter computation time. Extensive experiments on both real-world and synthetic graphs demonstrate the performance superiority of SCAN++ over existing approaches.

To obtain high PageRank score nodes, the original approach iteratively computes the Page-Rank score of each node until convergence by using the whole graph. If the graph is large, this approach is infeasible due to its high computational cost. The goal of this study is to find top-k Page\-Rank score nodes efficiently for a given graph without sacrificing accuracy. Our solution, F-Rank, is based on two ideas: (1) It iteratively estimates lower/upper bounds of Page\-Rank scores, and (2) It constructs subgraphs in each iteration by pruning unnecessary nodes and edges to identify top-k nodes. Our theoretical analysis shows that F-Rank guarantees result exactness. Experiments show that F-Rank finds top-k nodes much faster than the original approach.

In AI and Web communities, modularity-based graph clustering algorithms are being applied to various applications. However, existing algorithms are not applied to large graphs because they have to scan all vertices/edges iteratively. The goal of this paper is to efficiently compute clusters with high modularity from extremely large graphs with more than a few billion edges. The heart of our solution is to compute clusters by incrementally pruning unnecessary vertices/edges and optimizing the order of vertex selections. Our experiments show that our proposal outperforms all other modularity-based algorithms in terms of computation time, and it finds clusters with high modularity.

Graphs are a fundamental data structure and have been employed to model objects as well as their relationships. The similarity of objects on the web (e.g., webpages, photos, music, micro-blogs, and social networking service users) is the key to identifying relevant objects in many recent applications. SimRank, proposed by Jeh and Widom, provides a good similarity score and has been successfully used in many applications such as web spam detection, collaborative tagging analysis, link prediction, and so on. SimRank computes similarities iteratively, and it needs O(N4T) time and O(N2) space for similarity computation where N and T are the number of nodes and iterations, respectively. Unfortunately, this iterative approach is computationally expensive. The goal of this work is to process top-k search and range search efficiently for a given node. Our solution, SimMat, is based on two ideas: (1) It computes the approximate similarity of a selected node pair efficiently in non-iterative style based on the Sylvester equation, and (2) It prunes unnecessary approximate similarity computations when searching for the high similarity nodes by exploiting estimations based on the Cauchy-Schwarz inequality. These two ideas reduce the time and space complexities of the proposed approach to O(Nn) where n is the target rank of the low-rank approximation (n ≪ N in practice). Our experiments show that our approach is much faster, by several orders of magnitude, than previous approaches in finding the high similarity nodes.

Personalized PageRank (PPR) has been successfully applied to various applications. In real applications, it is important to set PPR parameters in an ad-hoc manner when finding similar nodes because of dynamically changing nature of graphs. Through interactive actions, interactive similarity search supports users to enhance the efficacy of applications. Unfortunately, if the graph is large, interactive similarity search is infeasible due to its high computation cost. Previous PPR approaches cannot effectively handle interactive similarity search since they need precomputation or approximate computation of similarities. The goal of this paper is to efficiently find the top-k nodes with exact node ranking so as to effectively support interactive similarity search based on PPR. Our solution is Castanet. The key Castanet operations are (1) estimate upper/lower bounding similarities iteratively, and (2) prune unnecessary nodes dynamically to obtain top-k nodes in each iteration. Experiments show that our approach is much faster than existing approaches.

Personalize PageRank (PPR) is an effective relevance (proximity) measure in graph mining. The goal of this paper is to efficiently compute single node relevance and top-k/highly relevant nodes without iteratively computing the relevances of all nodes. Based on a "random surfer model", PPR iteratively computes the relevances of all nodes in a graph until convergence for a given user preference distribution. The problem with this iterative approach is that it cannot compute the relevance of just one or a few nodes. The heart of our solution is to compute single node relevance accurately in non-iterative manner based on sparse matrix representation, and to compute top-k/highly relevant nodes exactly by pruning unnecessary relevance computations based on upper/lower relevance estimations. Our experiments show that our approach is up to seven orders of magnitude faster than the existing alternatives.

Distributed stream processing engines (DSPEs) have recently been studied to meet the needs of continuous query processing. Because they are built on the cooperation of several stream processing engines (SPEs), node failures cause the whole system to fail. This paper proposes a new high-availability scheme called Adaptive Semi-Active Standby (A-SAS). A-SAS enables adaptive tradeoff between bandwidth usage and recovery time. This paper presents the properties of A-SAS and experimental results that suggest A-SAS effectiveness.