Recommender systems are increasingly spreading to different areas like e-commerce or video streaming to alleviate information overload. One of the most fundamental methods for recommendation is Collaborative Filtering (CF), which leverages historical user-item interactions to infer user preferences. In recent years, Graph Neural Networks (GNNs) have been extensively studied to capture graph structures in CF tasks. Despite this remarkable progress, local structure modeling and embedding distortion still remain two notable limitations in the majority of GNN-based CF methods. Therefore, in this paper, we propose a novel Hyperbolic Graph Transformer architecture, to tackle the long-tail problems in CF tasks. Specifically, the proposed framework is comprised of two essential modules: 1) Local Hyperbolic Graph Convolutional Network (LHGCN), which performs graph convolution entirely in the hyperbolic manifold and captures the local structure of each node; 2) Hyperbolic Transformer, which is comprised of hyperbolic cross-attention mechanisms to capture global information. Furthermore, to enable its feasibility on large-scale data, we introduce an unbiased approximation of the cross-attention for linear computational complexity, with a theoretical guarantee in approximation errors. Empirical experiments demonstrate that our proposed model outperforms the leading collaborative filtering methods and significantly mitigates the long-tail issue in CF tasks. Our implementations are available in https://github.com/EnkiXin/Hgformer.

With the development of smart-phones, the number of smart-phone applications (apps) has exploded in recent years, making it time-consuming and labor-intensive for users to read the reviews and select the apps they really need. Therefore, it is a good solution to infer users’ preferences from user-app interactions and recommend it. However, most of the smart-phone applications are free to use and the method to evaluate users’ preferences are different from that of the subscription products. For this reason, we redefined heavy user of apps and use it to determine whether a user prefer an app or not.In the field of recommender system, one of the most popular ways is to use graph neural network (GNN) for prediction. GNN techniques have been demonstrated to be efficient in representation learning for graphs in various domains because most of the data in recommendation has essentially a graph structure. Besides, as real-life dataset always conforms a long-tail distribution, which means a small portion of classes have massive sample points but the others have only few samples. It will induce a good performance on the head samples but a poor performance on the tail samples. To enhance the representation ability of the models, one of the most accepted way is to implement contrastive learning(CL). In recent years, graph contrastive learning also achieves great success. However, there are relatively few researches implement contrastive learning on a knowledge graph. Therefore, we proposed a f our-l evel g raph c ontrastive l earning structure (FLGCL) and a structure-aware graph augmentation method for recommendation.For the task of app recommender systems, there have already been some researches that applied GNN. Although app dataset conforms a typical long-tail distribution, few researchers tested the feasibility of CL on the app dataset. To fill this research gap, we firstly proposed a novel way to model the interactions between users and apps as well as the relationships between different entities as a knowledge graph. We call it app knowledge graph(AKG). Then, we implemented FLGCL on the AKG. And in order to find out the versatility of FLGCL, we also implemented the experiments on the MovieLens Dataset. We find that FLGCL outperforms all the baseline models.

Carpooling, a transportation service that encourages employees to pick up and drop off co workers while driving to and from work, has the potential to decrease the number of private cars used to commute, eases commuter traffic congestion, and reduce CO$_{2}$emissions. Despite this potential situation of severe traffic congestion in Japan, little work has gone into developing carpooling specifically for commuting with co-workers scenarios. To build a carpooling system that accommodates Japanese unique culture and regulations, receptivity, safety, and profitability would be essential success factors. A carpooling problem (CPP) is proposed in this article with a focus on safety to discover a safe route for each driver that picks up and drops off co-workers and drives to and from their workspace while avoiding high accident-frequency locations. The CPP defines the subsets of employees sharing each car and the routes the drivers should take to optimize and minimize the total distance. Accident location data define the risk and driving competence determined by the classification of driver’s license and grade of automobile insurance; then, a driver’s optimal route minimizes risk while decreasing the total distance sought in deriving the CPP. The effectiveness of the proposed CPP was demonstrated by an experiment using actual accident data. This article also reports the small-scale proof-of-concept (PoC) study conducted to verify the efficacy of the proposed CPP and highlight issues with its practical application. Ten employees with five drivers and five co-workers commuted via carpooling for two weeks using a mobile application with the CPP developed independently. Through the questionnaire survey conducted after the PoC, we validated the need for carpooling. We also identified some challenges: safe map navigation, incentives for the driver, and adaptation to Japanese culture when the carpooling system is in practical use.

Restaurant sales forecasting is an important task for management of restaurants. Precise forecasting results of the restaurant sales can help to improve the revenue as well as the level of service. The methods based on a manager’s experience and basic statistic methods have been hard to get an accurate result for complicated features of this task. With the development of the neural network, it is possible to let the forecasting model to take a great amount of data into consideration and deal with complicated relationships. However, there are still two challenges in this task: the first one is that the features for restaurant sales forecasting have interaction effects on each other. Although the multiple layers of non-linear neural networks can learn the interaction effects to a certain extent, it was known to be inefficient in learning multiplicative feature interactions. The second one is that the data from a single store are not enough to train the model. While the model constructed from several stores located in the same area is expected to achieve a better result, these data will sometimes make result worse because of the different surrounding states and characteristics of customers for the stores. In order to tackle these two tasks, we introduced a novel feature interaction learning mechanism for the restaurant sales forecasting, where the features are divided into two categories that have a direct and indirect impact on sales. Moreover, by using actual data, we evaluated the proposed method improved the forecasting accuracy compared with other models.

Given a directed graph with a capacity and a transit time for each arc and with single source and single sink nodes, the quickest flow problem is to find the minimum time horizon to send a given amount of flow from the source to the sink. This is one of the fundamental dynamic flow problems. Parametric search is one of the basic approaches to solving the problem. Recently, Lin and Jaillet (SODA, 2015) proposed an algorithm whose time complexity is the same as that of the minimum cost flow algorithm. Their algorithm employs a cost scaling technique, and its time complexity is weakly polynomial time. In this article, we modify their algorithm by adopting a technique to construct a strongly polynomial time algorithm for solving the minimum cost flow problem. The proposed algorithm runs in O time, where n and m are the numbers of nodes and arcs, respectively. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(2), 179–188 2017

Virtual Machine(VM)-based flexible capacity management is an effective scheme to reduce total power consumption in the data centers. However, there remain the following issues, trade-off between power-saving and user experience, decision on VM packing plans within a feasible calculation time, and collision avoidance for multiple VM live migration processes. In order to resolve these issues, we propose two VM packing algorithms, a matching-based (MBA) and a greedy-type heuristic (GREEDY). MBA enables to decide an optimal plan in polynomial time, while GREEDY is an aggressive packing approach faster than MBA. We investigate the basic performance and the feasibility of proposed algorithms under both artificial and realistic simulation scenarios, respectively. The basic performance experiments show that the algorithms reduce total power consumption by between 18% and 50%, and MBA makes suitable VM packing plans within a feasible calculation time. The feasibility experiments show that the proposed algorithms are feasible to make packing plans for an actual supercomputer, and GREEDY has the advantage in power consumption, but MBA shows the better performance in user experience.

Abstract Gossiping is an extensively investigated information dissemination process. In gossiping, every vertex holds a message that has to be transmitted to all other vertices. This article deals with k‐failure tolerant gossiping, which investigates the minimum number of transmissions (calls) required by the communication process, provided that at most k transmissions may fail. We show new bounds for the number of transmissions, an improvement over previous results if k is sufficiently large. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

This paper presents a new strongly polynomial cut canceling algorithm for minimum cost submodular flow. The algorithm is a generalization of our similar cut canceling algorithm for ordinary min-cost flow. The algorithm scales a relaxed optimality parameter and creates a second, inner relaxation that is a kind of submodular max flow problem. The outer relaxation uses a novel technique for relaxing the submodular constraints that allows our previous proof techniques to work. The algorithm uses the min cuts from the max flow subproblem as the relaxed most positive cuts it chooses to cancel. We show that this algorithm needs to cancel only ${\mathrm O}(n^3)$ cuts per scaling phase, where n is the number of nodes. Furthermore, we show how to slightly modify this algorithm to get a strongly polynomial running time. Finally, we briefly show how to extend this algorithm to the separable convex cost case and that the same technique can be used to construct a polynomial time maximum mean cut canceling algorithm for submodular flow.

Abstract Let G = (N, A) be a directed graph of n nodes and m arcs with an upper bound u ∈ ℤA. Given an s—t cut S0, the minimax inverse minimum‐cut problem (MIMC) is to find a modified upper bound ũ ∈ ℝA such that S0 is a minimum cut for ũ and max {|uij − ũij‖(i, j) ∈ A} is minimum. This paper shows that the MIMC is closely related to the maximum mean‐cut problem. By applying a parametric search for maximum mean‐cut problems, the MIMC can be solved as a sequence of O(n) minimum s—t cut problems or in O(min {n2/3, m1/2}m log (n2/m) log n log (nU)) time, where U is the maximum value of u. © 2002 John Wiley & Sons, Inc.

The tree center problems are designed to find a subtree minimizing the maximum distance from any vertex. This paper shows that these problems in a tree network are related to the bottleneck knapsack problems and presents linear-time algorithms for the tree center problems by using the relation. © 1997 John Wiley & Sons, Inc. Networks, 29: 107–110, 1997