In this paper, we consider the problem of learning a tree graph structure that represents the statistical data dependency among nodes for a set of data samples generated by nodes, which provides the basic structure to perform a probabilistic inference task. Inference in the data graph includes marginal inference and maximum a posteriori (MAP) estimation, and belief propagation (BP) is a commonly used algorithm to compute the marginal distribution of nodes via message-passing, incurring non-negligible amount of communication cost. We inevitably have the trade-off between the inference accuracy and the message-passing cost because the learned structure of data dependency and physical connectivity graph are often highly different. In this paper, we formalize this trade-off in an optimization problem which outputs the data dependency graph that jointly considers learning accuracy and message-passing costs. We focus on two popular implementations of BP,ASYNC-BPandSYNC-BP, which have different message-passing mechanisms and cost structures. InASYNC-BP, we propose a polynomial-time learning algorithm that is optimal, motivated by finding a maximum weight spanning tree of a complete graph. InSYNC-BP, we prove the NP-hardness of the problem and propose a greedy heuristic. For both BP implementations, we quantify how the error probability that the learned cost-efficient data graph differs from the ideal one decays as the number of data samples grows, using the large deviation principle, which provides a guideline on how many samples are necessary to obtain a certain trade-off. We validate our theoretical findings through extensive simulations, which confirms that it has a good match.

Hypergraphs provide a natural way of representing group relations, whose complexity motivates an extensive array of prior work to adopt some form of abstraction and simplification of higher-order interactions. However, the following question has yet to be addressed: How much abstraction of group interactions is sufficient in solving a hypergraph task, and how different such results become across datasets? This question, if properly answered, provides a useful engineering guideline on how to trade off between complexity and accuracy of solving a downstream task. To this end, we propose a method of incrementally representing group interactions using a notion of n-projected graph whose accumulation contains information on up to n-way interactions, and quantify the accuracy of solving a task as n grows for various datasets. As a downstream task, we consider hyperedge prediction, an extension of link prediction, which is a canonical task for evaluating graph models. Through experiments on 15 real-world datasets, we draw the following messages: (a) Diminishing returns: small n is enough to achieve accuracy comparable with near-perfect approximations, (b) Troubleshooter: as the task becomes more challenging, larger n brings more benefit, and (c) Irreducibility: datasets whose pairwise interactions do not tell much about higher-order interactions lose much accuracy when reduced to pairwise abstractions.

Fog computing is a paradigm which brings computing, storage, and networking closer to end users and end devices for better service provisioning. One of the crucial factors in the success of fog computing is on how to incentivize the individual users' edge resources and provide them to end users such that fog computing is economically beneficial to all involved economic players. In this paper, we model and analyze a market of fog computing, from which we aim at drawing practical implications to uncover how the fog computing market should operate. To this end, we conduct an economic analysis of such user-oriented fog computing by modeling a market consisting of Infrastructure and Service Provider (ISP), end Service Users (SUs), and Edge Resource Owners (EROs) as a non-cooperative game. In this market, ISP, which provides a platform for fog computing, behaves as a mediator or a broker which leases EROs' edge resources and provides various services to SUs. In our model, a two-stage dynamic game is used where in each stage, there exists a dynamic game, one for between ISP and EROs and another for between ISP and SUs, to model the market more practically. Despite this complex game structure, we provide a closed-form equilibrium analysis which gives an insight on how much economic benefit is obtained by ISP, SUs, and EROs from user-oriented fog computing under what conditions, and we figure out the economic factors that have a significant impact on the success of fog computing.

We consider the Markov Decision Process (MDP) of selecting a subset of items at each step, termed the Select-MDP (S-MDP). The large state and action spaces of S-MDPs make them intractable to solve with typical reinforcement learning (RL) algorithms especially when the number of items is huge. In this paper, we present a deep RL algorithm to solve this issue by adopting the following key ideas. First, we convert the original S-MDP into an Iterative Select-MDP (IS-MDP), which is equivalent to the S-MDP in terms of optimal actions. IS-MDP decomposes a joint action of selecting K items simultaneously into K iterative selections resulting in the decrease of actions at the expense of an exponential increase of states. Second, we overcome this state space explosion by exploiting a special symmetry in IS-MDPs with novel weight shared Q-networks, which provably maintain sufficient expressive power. Various experiments demonstrate that our approach works well even when the item space is large and that it scales to environments with item spaces different from those used in training.

Fog computing is a paradigm which brings computing, storage, and networking closer to end users and devices for better service provisioning. One of the crucial factors towards the success of fog computing is how to incentivize the individual users' edge resources, thereby opening the era of user- participated fog computing. In this paper, we provide an economic analysis of such user-oriented fog computing by modeling a market consisting of ISP (Infrastructure and Service Provider), SUs (end Service Users), and EROs (Edge Resource Owners) as a noncooperative game. In this market, ISP, which provides a platform of fog computing, behaves as a mediator or a broker to lease the edge resources from EROs and provide various services to SUs. In our game formulation, a two-stage dynamic game is used, where in each stage there exists another dynamic game, one for between ISP and EROs and another for between ISP and SUs, to model the market more practically. Despite this complex game structure, we provide a closed- form equilibrium analysis, which gives an insight of how much economic benefits are obtained by ISP, SUs, and EROs under what conditions.

In this paper, we consider the problem of recovering a graph that represents the statistical data dependency among nodes for a set of data samples generated by nodes, which provides the basic structure to perform an inference task, such as MAP (maximum a posteriori). This problem is referred to as structure learning. When nodes are spatially separated in different locations, running an inference algorithm requires a non-negligible amount of message passing, incurring some communication cost. We inevitably have the trade-off between the accuracy of structure learning and the cost we need to pay to perform a given message-passing based inference task because the learnt edge structures of data dependency and physical connectivity graph are often highly different. In this paper, we formalize this trade-off in an optimization problem which outputs the data dependency graph that jointly considers learning accuracy and message-passing cost. We focus on a distributed MAP as the target inference task due to its popularity, and consider two different implementations, ASYNC-MAP and SYNC-MAP that have different message-passing mechanisms and thus different cost structures. In ASYNC-MAP, we propose a polynomial time learning algorithm that is optimal, motivated by the problem of finding a maximum weight spanning tree. In SYNC-MAP, we first prove that it is NP-hard and propose a greedy heuristic. For both implementations, we then quantify how the probability that the resulting data graphs from those learning algorithms differ from the ideal data graph decays as the number of data samples grows, using the large deviation principle, where the decaying rate is characterized by some topological structures of both original data dependency and physical connectivity graphs as well as the degree of the trade-off, which provides some guideline on how many samples are necessary to obtain a certain learning accuracy. We validate our theoretical findings through extensive simulations, which confirm that it has a good match.