Graph embedding is the process of obtaining a vector representation of graph nodes. The representation obtained by graph embedding is highly versatile. It can be used for various tasks, such as recommendation and clustering tasks. However, there are only a few methods that incorporate attributes indicating node characteristics, such as user gender, age, or product category, into graph embedding. Therefore, we hypothesize that nodes with the same attribute are often connected to the same node. Consequently, we propose two methods for graph embedding, parallel and serial, that use metric learning to reflect attribute data in node features. The proposed method can be applied to any graph embedding and metric learning method, and thus can also be applied to many new methods yet to be developed. Numerical experimental results show that the proposed method using node attributes is superior to the existing methods in both AUROC and accuracy.

Abstract The studies of browsing behavior have gained increasing attention in web analysis for providing better service. Most of the conventional approaches focus on simple indices such as average dwell time and conversion rate. These indices make similar evaluations to websites even if their features are significantly different. Moreover, such statistical indices are not sensitive to the dynamics of users’ interests. In this paper, we propose a new framework for measuring a website’s attractiveness that takes into account both the distribution and dynamics of users’ interests. Within the framework, we define a new index for the website, called Attractiveness Factor, which evaluates the degree of users’ attention. It consists of three procedures: First, we capture the transition of users’ interests during browsing by solving a nonnegative matrix factorization and constrained network flow problems. To accommodate multiple types of interests of a user, we applied a soft clustering as opposed to a hard clustering to model attributes of users and websites. Second, for each website, the feature of each cluster is obtained by fitting the dwell time distribution with Weibull distribution. Finally, we calculate Attractiveness Factor of a website by applying the results of clustering and fitting. Attractiveness Factor depends on the distribution of the dwell time of users interested in the website, which reflects the change of interest of users. Numerical experiments with real web access data of Yahoo Japan News are conducted by solving extremely large-scale optimization problems. They show that Attractiveness Factor captures more exceptional information about browsing behavior more effectively than well-used indices. Attractive factors give low ratings to category pages; however, it can assign high ratings to websites that attract many people, such as hot topic news about the 2018 FIFA World Cup, Japan’s new imperial era’ REIWA,’ and North Korea—the United States Hanoi Summit. Moreover, we demonstrate that Attractiveness Factor can detect the tendency of users’ attention to each website at a given time interval of the day.

One of the most critical problems in bike-sharing services is a bicycle repositioning problem, which is how service providers must relocate their bicycles to maintain the quality of service. In this paper, we propose an end-to-end approach for the bike repositioning problem, which realizes the operator-feasible repositioning plan with cooperation among multiple trucks. Our proposed algorithm consists of three procedures. First, we predict the number of rented and returned bicycles at each station with a deep learning based on the bicycle usage information. Second, we determine the optimal number of bicycles to satisfy the availability of each station by solving an integer optimization problem. Finally, we solve the vehicle routing problem formulated as another integer optimization problem. Based on our algorithm, service operators can actually perform a relocation task based with a reference to the truck capacity, routes, and the number of bicycles to be loaded and unloaded. We demonstrate the applicability of our algorithm in the real world through numerical experiments on the real bicycle data of a Japanese company.

Cyber-Physical Systems (CPSs) are attracting significant attention from a number of industries, including social infrastructure, manufacturing, retail, among others. We can easily gather big datasets of people and transportation movements by utilizing camera and sensor technologies, and create new industrial applications by optimizing and simulating social mobility in the cyberspace. In this paper, we develop the system which automatically performs a series of processes, including object detection, multiple object tracking, and mobility optimization. The mobility of humans and objects is one of the essential components in the real world. Therefore, our system can be widely applied to various application fields. Our major contributions to this paper are remarkable performance improvement of multiple object tracking and building the new mobility optimization engine. In the former, we improve the multiple object tracker using K-Shortest Paths (KSP), which achieves significant data reduction and acceleration by specifying and deleting unnecessary nodes. Numerical experiments show that our proposed tracker is over three times faster than the original KSP tracker while keeping the accuracy. We formulate the mobility optimization problem as the SATisfiability problem (SAT) and the Integer Programming problem (IP) in the latter. Numerical experiments demonstrate that the total transit time can be reduced from 30 s to 10 s. We discuss the characteristics of solutions obtained by the two formulations. We can finally select the appropriate optimization method according to the constraints of calculation time and accuracy for real applications.

In this paper, we propose a practical approach to evacuation planning by utilizing network flow and deep learning algorithms. In recent years, large amounts of data are rapidly being stored in the cloud system, and effective data utilization for solving real-world problems is required more than ever. Hierarchical Data Analysis and Optimization System (HDAOS) enables us to select appropriate algorithms according to the degree of difficulty in solving problems and a given time for the decision-making process, and such selection helps address real-world problems. In the field of emergency evacuation planning, however, the Lexicographically Quickest Flow (LQF) algorithm has an extremely long computation time on a large-scale network, and is therefore not a practical solution. For Osaka city, which is the second-largest city in Japan, we must solve the maximum flow problems on a large-scale network with over 8.3M nodes and 32.8M arcs for obtaining an optimal plan. Consequently, we can feed back nothing to make an evacuation plan. To solve the problem, we utilize the optimal solution as training data of a deep Convolutional Neural Network (CNN). We train a CNN by using the results of the LQF algorithm in normal time, and in emergencies predict the evacuation completion time (ECT) immediately by the well-learned CNN. Our approach provides almost precise ECT, achieving an average regression error of about 2%. We provide several techniques for combining LQF with CNN and addressing numerous movements as CNN's input, which has rarely been considered in previous studies. Hodge decomposition also demonstrates that LQF is efficient from the standpoint of the total distance traveled by all evacuees, which reinforces the validity of the method of utilizing the LQF algorithm for deep learning.

There are many large-scale graphs in real world such as Web graphs and social graphs. The interest in large-scale graph analysis is growing in recent years. Breadth-First Search (BFS) is one of the most fundamental graph algorithms used as a component of many graph algorithms. Our new method for distributed parallel BFS can compute BFS for one trillion vertices graph within half a second, using large supercomputers such as the K-Computer. By the use of our proposed algorithm, the K-Computer was ranked 1st in Graph500 using all the 82,944 nodes available on June and November 2015 and June 2016 38,621.4 GTEPS. Based on the hybrid BFS algorithm by Beamer (Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, IPDPSW ’13, IEEE Computer Society, Washington, 2013 ), we devise sets of optimizations for scaling to extreme number of nodes, including a new efficient graph data structure and several optimization techniques such as vertex reordering and load balancing. Our performance evaluation on K-Computer shows that our new BFS is 3.19 times faster on 30,720 nodes than the base version using the previously known best techniques.

As the power consumption of HPC systems will be a primary constraint for exascale computing, a main objective in HPC communities is recently becoming to maximize power efficiency (i.e., performance per watt) rather than performance. Although programmers have spent a considerable effort to improve performance by tuning HPC programs at a code level, tunings for improving power efficiency is now required. In this work, we select two representative HPC programs (Graph500 and SDPARA) and evaluate how traditional code-level performance tunings applied to these programs affect power efficiency. We also investigate the impacts of the tunings on power efficiency at various operating frequencies of CPUs and/or GPUs. The results show that the tunings significantly improve power efficiency, and different types of tunings exhibit different trends in power efficiency by varying CPU frequency. Finally, the scalability and power efficiency of state-of-the-art Graph500 implementations are explored on both a single-node platform and a 960-node supercomputer. With their high scalability, they achieve 27.43 MTEPS/Watt with 129.76 GTEPS on the single-node system and 4.39 MTEPS/Watt with 1,085.24 GTEPS on the supercomputer.

Breadth-First Search(BFS) is one of the most fundamental graph algorithms used as a component of many graph algorithms. Our new method for distributed parallel BFS can compute BFS for one trillion vertices graph within half a second, using large supercomputers such as the K-Computer. By the use of our proposed algorithm, the K-Computer was ranked 1st in Graph500 using all the 82,944 nodes available on June and November 2015 and June 2016 38,621.4 GTEPS. Based on the hybrid-BFS algorithm by Beamer[3], we devise sets of optimizations for scaling to extreme number of nodes, including a new efficient graph data structure and optimization techniques such as vertex reordering and load balancing. Performance evaluation on the K shows our new BFS is 3.19 times faster on 30,720 nodes than the base version using the previously-known best techniques.

We introduce a memory efficient implementation for the NVM-based Hybrid BFS algorithm that merges redundant data structures to a single graph data structure, while offloading infrequent accessed graph data on NVMs based on the detailed analysis of access patterns, and demonstrate extremely fast BFS execution for large-scale unstructured graphs whose size exceed the capacity of DRAM on the machine. Experimental results of Kronecker graphs compliant to the Graph500 benchmark on a 2-way INTEL Xeon E5-2690 machine with 256 GB of DRAM show that our proposed implementation can achieve 4.14 GTEPS for a SCALE31 graph problem with 231vertices and 235edges, whose size is 4 times larger than the size of graphs that the machine can accommodate only using DRAM with only 14.99 % performance degradation. We also show that the power efficiency of our proposed implementation achieves 11.8 MTEPS/W. Based on the implementation, we have achieved the 3rd and 4th position of the Green Graph500 list (2014 June) in the Big Data category.

The breadth-first search (BFS) is one of the most important kernels in graph theory. The Graph500 benchmark measures the performance of any supercomputer performing a BFS in terms of traversed edges per second (TEPS). Previous studies have proposed hybrid approaches that combine a well-known top-down algorithm and an efficient bottom-up algorithm for large frontiers. This reduces some unnecessary searching of outgoing edges in the BFS traversal of a small-world graph, such as a Kronecker graph. In this paper, we describe a highly efficient BFS using column-wise partitioning of the adjacency list while carefully considering the non-uniform memory access (NUMA) architecture. We explicitly manage the way in which each working thread accesses a partial adjacency list in local memory during BFS traversal. Our implementation has achieved a processing rate of 11.15 billion edges per second on a 4-way Intel Xeon E5-4640 system for a scale-26 problem of a Kronecker graph with 226vertices and 230edges. Not all of the speedup techniques in this paper are limited to the NUMA architecture system. With our winning Green Graph500 submission of June 2013, we achieved 64.12 GTEPS per kilowatt hour on an ASUS Pad TF700T with an NVIDIA Tegra 3 mobile processor.