In recent years, we have seen the success of network representation learning (NRL) methods in diverse domains ranging from computational chemistry to drug discovery and from social network analysis to bioinformatics algorithms. However, each such NRL method is typically prototyped in a programming environment familiar to the developer. Moreover, such methods rarely scale out to large-scale networks or graphs. Such restrictions are problematic to domain scientists or end-users who want to scale a particular NRL method-of-interest on large graphs from their specific domain. In this work, we present a novel system, WebMILE to democratize this process. WebMILE can scale an unsupervised network embedding method written in the user's preferred programming language on large graphs. It provides an easy-to-use Graphical User Interface (GUI) for the end-user. The user provides the necessary input (embedding method file, graph, required packages information) through a simple GUI, and WebMILE executes the input network embedding method on the given input graph. WebMILE leverages a pioneering multi-level method, MILE (alternatively DistMILE if the user has access to a cluster), that can scale a network embedding method on large graphs. The language agnosticity is achieved through a simple Docker interface. In this demonstration, we will showcase how a domain scientist or end-user can utilize WebMILE to rapidly prototype and learn node embeddings of a large graph in a flexible and efficient manner - ensuring the twin goals of high productivity and high performance.

Darknet market forums are frequently used to exchange illegal goods and services between parties who use encryption to conceal their identities.The Tor network is used to host these markets, which guarantees additional anonymization from IP and location tracking, making it challenging to link across malicious users using multiple accounts (sybils).Additionally, users migrate to new forums when one is closed further increasing the difficulty of linking users across multiple forums.We develop a novel stylometry-based multitask learning approach for natural language and model interactions using graph embeddings to construct low-dimensional representations of short episodes of user activity for authorship attribution.We provide a comprehensive evaluation of our methods across four different darknet forums demonstrating its efficacy over the state-of-the-art, with a lift of up to 2.5X on Mean Retrieval Rank and 2X on Recall@10.

Scalable graph embedding on large networks is challenging because of the complexity of graph structures and limited computing resources. Recent research shows that the multi-level framework can enhance the scalability of graph embedding methods with little loss of quality. In general, methods using this framework first coarsen the original graph into a series of smaller graphs then learn the representations of the original graph from them in an efficient manner. However, to the best of our knowledge, most multi-level based methods do not have a parallel implementation. Meanwhile, the emergence of high-performance computing for machine learning provides an opportunity to boost graph embedding by distributed computing. In this paper, we propose a Distributed MultI -Level Embedding (DistMILE11Our code is available at https://github.com/heyuntian/DistMILE) framework to further improve the scalability of graph embedding. DistMILE leverages a novel shared-memory parallel algorithm for graph coarsening and a distributed training paradigm for embedding refinement. With the advantage of high-performance computing techniques, Dist-MILE can smoothly scale different base embedding methods over large networks. Our experiments demonstrate that DistMILE learns representations of similar quality with respect to other baselines, while reduces the time of learning embeddings on large-scale networks to hours. Results show that DistMILE can achieve up to 28 x speedup compared with a popular multi-level embedding framework MILE and expedite existing embedding methods with 40 x speedup.

We propose the first budget-limited multi-armed bandit (BMAB) algorithm subject to a union of matroid constraints in arm pulling, while at the same time achieving differential privacy. Our model generalizes the arm-pulling models studied in prior BMAB schemes, and it can be used to address many practical problems such as network backbone construction and dynamic pricing in crowdsourcing. We handle the exploitation versus exploration tradeoff in our BMAB problem by exploiting the combinatorial structures of matroids, and reduce the searching complexity of arm selection based on a divide-and-conquer approach. Our algorithm achieves a uniform logarithmic regret bound with respect to B and ɛ-differential privacy, where B is the budget for pulling the arms with random costs. Without differential privacy, our algorithm achieves a uniform logarithmic regret bound with respect to B, which advances the asymptotic regret bounds achieved by prior BMAB algorithms. We performed side-by-side comparisons with prior schemes in our experiments. Experimental results show that our purely-combinatorial algorithm not only achieves significantly better regret performance, but also is more than 20 times faster than prior BMAB schemes, which use time-consuming LP-solving techniques.

We study the min-cost seed selection problem in online social networks for viral marketing, where the goal is to select a set of seed nodes with the minimum total cost such that the expected number of influenced nodes in the network exceeds a predefined threshold. We propose several algorithms that outperform the previous studies both on the theoretical approximation ratio and on the experimental performance. In the case where the nodes have heterogeneous costs, our algorithms are the first bi-criteria approximation algorithms with polynomial running time and provable approximation ratio. In the case where the users have uniform costs, our algorithms achieve logarithmic approximation ratio and provable time complexity which is smaller than that of the existing algorithms in orders of magnitude. We conduct extensive experiments using real social networks. The experimental results show that, our algorithms significantly outperform the existing algorithms both on the total cost and on the running time, and also scale well to billion-scale networks.

We consider the edge uncertainty in an undirected graph and study the k -median (resp. k -center) problems, where the goal is to partition the graph nodes into k clusters such that the average (resp. minimum) connection probability between each node and its cluster's center is maximized. We analyze the hardness of these problems, and propose algorithms that provide considerably improved approximation guarantees than the existing studies do. Specifically, our algorithms offer (1 -- 1/e)-approximations for the k -median problem and (OPTck)-approximations for the k -center problem, where OPTck is the optimal objective function value for k -center. In addition, our algorithms incorporate several non-trivial optimizations that significantly enhance their practical efficiency. Extensive experimental results demonstrate that our algorithms considerably outperform the existing methods on both computation efficiency and the quality of clustering results.

Recently, the proliferation of event-based social services has made it possible for organizing personalized offline events through the users' information shared online. In this paper, we study the budget-constrained influential social event organization problem, where the goal is to select a group of influential users with required features to organize a social event under a budget B. We show that our problem is NP-hard and can be formulated as a submodular maximization problem with mixed packing and covering constraints. We then propose several polynomial time algorithms for our problem with provable approximation ratios, which adopt a novel “surrogate optimization” approach and the method of reverse-reachable set sampling. Moreover, we also consider the case where the influence spread function is unknown and can be arbitrarily selected from a set of candidate submodular functions, and extend our algorithms to address a “robust influential event organization” problem under this case. Finally, we conduct extensive experiments using real social networks to test the performance of our algorithms, and the experimental results demonstrate that our algorithms significantly outperform the prior studies both on the running time and on the influence spread.

Recently, the proliferation of event-based social services has made it possible for organizing personalized offline events through the users' information shared online. In this paper, we study the budget-constrained influential social event organization problem, where the goal is to select a group of influential users with required features to organize a social event under a budget B. We show that our problem is NP-hard and can be formulated as a submodular maximization problem with mixed packing and covering constraints. We then propose several polynomial time algorithms for our problem with provable approximation ratios, which adopt a novel "surrogate optimization approach and the method of reverse-reachable set sampling. Compared with some related work that can only handle special cases of our problem but with exponential time complexity, our algorithms are much more efficient, and their superiorities on both the running time and the influence spread are demonstrated through extensive experiments using real social networks."

Mobile crowdsourcing has been proposed as a promising approach for urban data collection, but it has also brought the critical problem of designing proper mechanisms to incentivize user participation. Most previous work on crowdsourcing incentivization has assumed that each user holds a single private cost for participation or behaves in a "win all or nothing" (a.k.a. "single-minded") manner. However, in some crowdsourcing applications such as Amazon's Mechanical Turk, the users are usually "multi-minded" in the sense that each of them holds heterogeneous private costs for different tasks and only performs a portion of her/his interested tasks according to the announced payments. To address this problem, we propose LIME, an onLine prIcing mechanism to incentivize Multi-minded usErs under the scenario where the users arrive sequentially in an arbitrary order. We show that the design of LIME involves solving a "dummy semi-bandits with multiple knapsacks and random costs" problem, which has not been investigated before, and we also prove that LIME achieves several desirable properties including computational efficiency, budget feasibility, truthfulness, individual rationality and low regret on the utility. Finally, the effectiveness of LIME as well as its superiorities over prior related work are demonstrated through extensive simulations.