Search

Literature search is one of the most important steps of academic research. With more than 100,000 papers published each year just in computer science, performing a complete literature search becomes a Herculean task. Some of the existing approaches and tools for literature search cannot compete with the characteristics of today’s literature, and they suffer from ambiguity and homonymy. Techniques based on citation information are more robust to the mentioned issues. Thus, we recently built a Web service called the advisor, which provides personalized recommendations to researchers based on their papers of interest. Since most recommendation methods may return redundant results, diversifying the results of the search process is necessary to increase the amount of information that one can reach via an automated search. This article targets the problem of result diversification in citation-based bibliographic search, assuming that the citation graph itself is the only information available and no categories or intents are known. The contribution of this work is threefold. We survey various random walk--based diversification methods and enhance them with the direction awareness property to allow users to reach either old, foundational (possibly well-cited and well-known) research papers or recent (most likely less-known) ones. Next, we propose a set of novel algorithms based on vertex selection and query refinement. A set of experiments with various evaluation criteria shows that the proposed γ-RLM algorithm performs better than the existing approaches and is suitable for real-time bibliographic search in practice. [ABSTRACT FROM AUTHOR]

The pervasive usage and reach of social media have attracted a surge of attention in the multimedia research community. Community discovery from social media has therefore become an important yet challenging issue. However, due to the subjective generating process, the explicitly observed communities (e.g., group-user and user-user relationship) are often noisy and incomplete in nature. This paper presents a novel approach to discovering communities from social media, including the group membership and user friend structure, by exploring a low-rank matrix recovery technique. In particular, we take Flickr as one exemplary social media platform. We first model the observed indicator matrix of the Flickr community as a summation of a low-rank true matrix and a sparse error matrix. We then formulate an optimization problem by regularizing the true matrix to coincide with the available rich context and content (i.e., photos and their associated tags). An iterative algorithm is developed to recover the true community indicator matrix. The proposed approach leads to a variety of social applications, including community visualization, interest group refinement, friend suggestion, and influential user identification. The evaluations on a large-scale testbed, consisting of 4,919 Flickr users, 1,467 interest groups, and over five million photos, show that our approach opens a new yet effective perspective to solve social network problems with sparse learning technique. Despite being focused on Flickr, our technique can be applied in any other social media community. [ABSTRACT FROM AUTHOR]

Multi-view clustering aims to capture the multiple views inherent information by identifying the data clustering that reflects distinct features of datasets. Since there is a consensus in literature that different views of a dataset share a common latent structure, most existing multi-view subspace learning methods rely on the nuclear norm to seek the low-rank representation of the underlying subspace. However, the nuclear norm often fails to distinguish the variance of features for each cluster due to its convex nature and data tends to fall in multiple non-linear subspaces for multi-dimensional datasets. To address these problems, we propose a new and novel multi-view clustering method (HL-L21-TLD-MSC) that unifies the Hyper-Laplacian (HL) and exclusive ℓ2,1 (L21) regularization with the Tensor Log-Determinant Rank Minimization (TLD) setting. Specifically, the hyper-Laplacian regularization maintains the local geometrical structure that makes the estimation prune to nonlinearities, and the mixed ℓ2,1 and ℓ1,2 regularization provides the joint sparsity within-cluster as well as the exclusive sparsity between-cluster. Furthermore, a log-determinant function is used as a tighter tensor rank approximation to discriminate the dimension of features. An efficient alternating algorithm is then derived to optimize the proposed model, and the construction of a convergent sequence to the Karush-Kuhn-Tucker (KKT) critical point solution is mathematically validated in detail. Extensive experiments are conducted on ten well-known datasets to demonstrate that the proposed approach outperforms the existing state-of-the-art approaches with various scenarios, in which, six of them achieve perfect results under our framework developed in this article, demonstrating highl effectiveness for the proposed approach. [ABSTRACT FROM AUTHOR]

Anomaly analytics is a popular and vital task in various research contexts that has been studied for several decades. At the same time, deep learning has shown its capacity in solving many graph-based tasks, like node classification, link prediction, and graph classification. Recently, many studies are extending graph learning models for solving anomaly analytics problems, resulting in beneficial advances in graph-based anomaly analytics techniques. In this survey, we provide a comprehensive overview of graph learning methods for anomaly analytics tasks. We classify them into four categories based on their model architectures, namely graph convolutional network, graph attention network, graph autoencoder, and other graph learning models. The differences between these methods are also compared in a systematic manner. Furthermore, we outline several graph-based anomaly analytics applications across various domains in the real world. Finally, we discuss five potential future research directions in this rapidly growing field. [ABSTRACT FROM AUTHOR]

At the heart of multi-agent systems is the ability to cooperate to improve the performance of individual agents and/or the system as a whole. While a widespread assumption in the literature is that such cooperation is essentially unrestricted, in many realistic settings this assumption does not hold. A highly influential approach for modelling such scenarios are graph-restricted games introduced by Myerson [36]. In this approach, agents are represented by nodes in a graph, edges represent communication channels, and a group can generate an arbitrary value only if there exists a direct or indirect communication channel between every pair of agents within the group. Two fundamental solution-concepts that were proposed for such games are the Myerson value and the Shapley value. While an algorithm has been developed to compute the Shapley value in arbitrary graph-restricted games, no such general-purpose algorithm has been developed for the Myerson value to date. With this in mind, we set out to develop for such games a general-purpose algorithm to compute the Myerson value, and a more efficient algorithm to compute the Shapley value. Since the computation of either value involves enumerating all connected induced subgraphs of the game's underlying graph, we start by developing an algorithm dedicated to this enumeration, and then we show empirically that it is faster than the state of the art in the literature. Finally, we present a sample application of both algorithms, in which we test the Myerson value and the Shapley value as advanced measures of node centrality in networks. [ABSTRACT FROM AUTHOR]

Learning-to-Rank (LtR) solutions are commonly used in large-scale information retrieval systems such as Web search engines, which have to return highly relevant documents in response to user query within fractions of seconds. The most effective LtR algorithms adopt a gradient boosting approach to build additive ensembles of weighted regression trees. Since the required ranking effectiveness is achieved with very large ensembles, the impact on response time and query throughput of these solutions is not negligible. In this article, we propose X-CLEaVER, an iterative meta-algorithm able to build more efficient and effective ranking ensembles. X-CLEaVER interleaves the iterations of a given gradient boosting learning algorithm with pruning and re-weighting phases. First, redundant trees are removed from the given ensemble, then the weights of the remaining trees are fine-tuned by optimizing the desired ranking quality metric. We propose and analyze several pruning strategies and we assess their benefits showing that interleaving pruning and re-weighting phases during learning is more effective than applying a single post-learning optimization step. Experiments conducted using two publicly available LtR datasets show that X-CLEaVER can be successfully exploited on top of several LtR algorithms as it is effective in optimizing the effectiveness of the learnt ensembles, thus obtaining more compact forests that hence are much more efficient at scoring time. [ABSTRACT FROM AUTHOR]

Matrix factorization is known to be an effective method for recommender systems that are given only the ratings from users to items. Currently, stochastic gradient (SG) method is one of the most popular algorithms for matrix factorization. However, as a sequential approach, SG is difficult to be parallelized for handling web-scale problems. In this article, we develop a fast parallel SG method, FPSG, for shared memory systems. By dramatically reducing the cache-miss rate and carefully addressing the load balance of threads, FPSG is more efficient than state-of-the-art parallel algorithms for matrix factorization. [ABSTRACT FROM AUTHOR]

This article deals with a decision-making problem concerning an agent who wants to choose a partner from multiple candidates for long-term collaboration. To choose the best partner, the agent can rely on prior information he knows about the candidates. However, to improve his decision, he can request additional information from information sources. Nonetheless, acquiring information from external information sources about candidates may be biased due to different personalities of the agent searching for a partner and the information source. In addition, information may be costly. Considering the bias and the cost of the information sources, the optimization problem addressed in this article is threefold: (1) determining the necessary amount of additional information, (2) selecting information sources from which to request the information, and (3) choosing the candidates on whom to request the additional information. We propose a heuristic to solve this optimization problem. The results of experiments on simulated and real-world domains demonstrate the efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

In this article, we study automated agents that are designed to encourage humans to take some actions over others by strategically disclosing key pieces of information. To this end, we utilize the framework of persuasion games—a branch of game theory that deals with asymmetric interactions where one player (Sender) possesses more information about the world, but it is only the other player (Receiver) who can take an action. In particular, we use an extended persuasion model, where the Sender’s information is imperfect and the Receiver has more than two alternative actions available. We design a computational algorithm that, from the Sender’s standpoint, calculates the optimal information disclosure rule. The algorithm is parameterized by the Receiver’s decision model (i.e., what choice he will make based on the information disclosed by the Sender) and can be retuned accordingly. We then provide an extensive experimental study of the algorithm’s performance in interactions with human Receivers. First, we consider a fully rational (in the Bayesian sense) Receiver decision model and experimentally show the efficacy of the resulting Sender’s solution in a routing domain. Despite the discrepancy in the Sender’s and the Receiver’s utilities from each of the Receiver’s choices, our Sender agent successfully persuaded human Receivers to select an option more beneficial for the agent. Dropping the Receiver’s rationality assumption, we introduce a machine learning procedure that generates a more realistic human Receiver model. We then show its significant benefit to the Sender solution by repeating our routing experiment. To complete our study, we introduce a second (supply--demand) experimental domain and, by contrasting it with the routing domain, obtain general guidelines for a Sender on how to construct a Receiver model. [ABSTRACT FROM AUTHOR]

We present a new algorithm for inferring the home location of Twitter users at different granularities, including city, state, time zone, or geographic region, using the content of users' tweets and their tweeting behavior. Unlike existing approaches, our algorithm uses an ensemble of statistical and heuristic classifiers to predict locations and makes use of a geographic gazetteer dictionary to identify place-name entities. We find that a hierarchical classification approach, where time zone, state, or geographic region is predicted first and city is predicted next, can improve prediction accuracy. We have also analyzed movement variations of Twitter users, built a classifier to predict whether a user was travelling in a certain period of time, and use that to further improve the location detection accuracy. Experimental evidence suggests that our algorithm works well in practice and outperforms the best existing algorithms for predicting the home location of Twitter users. [ABSTRACT FROM AUTHOR]

Traditional approaches to community detection, as studied by physicists, sociologists, and more recently computer scientists, aim at simply partitioning the social network graph. However, with the advent of online social networking sites, richer data has become available: beyond the link information, each user in the network is annotated with additional information, for example, demographics, shopping behavior, or interests. In this context, it is therefore important to develop mining methods which can take advantage of all available information. In the case of community detection, this means finding good communities (a set of nodes cohesive in the social graph) which are associated with good descriptions in terms of user information (node attributes). Having good descriptions associated to our models make them understandable by domain experts and thus more useful in real-world applications. Another requirement dictated by real-world applications, is to develop methods that can use, when available, any domain-specific background knowledge. In the case of community detection the background knowledge could be a vague description of the communities sought in a specific application, or some prototypical nodes (e.g., good customers in the past), that represent what the analyst is looking for (a community of similar users). Towards this goal, in this article, we define and study the problem of finding a diverse set of cohesive communities with concise descriptions. We propose an effective algorithm that alternates between two phases: a hill-climbing phase producing (possibly overlapping) communities, and a description induction phase which uses techniques from supervised pattern set mining. Our framework has the nice feature of being able to build well-described cohesive communities starting from any given description or seed set of nodes, which makes it very flexible and easily applicable in real-world applications. Our experimental evaluation confirms that the proposed method discovers cohesive communities with concise descriptions in realistic and large online social networks such as DELICIOUS, FLICKR, and LASTFM. [ABSTRACT FROM AUTHOR]

The effects of social influence and homophily suggest that both network structure and node-attribute information should inform the tasks of link prediction and node-attribute inference. Recently, Yin et al. [2010a, 2010b] proposed an attribute-augmented social network model, which we call Social-Attribute Network (SAN), to integrate network structure and node attributes to perform both link prediction and attribute inference. They focused on generalizing the random walk with a restart algorithm to the SAN framework and showed improved performance. In this article, we extend the SAN framework with several leading supervised and unsupervised link-prediction algorithms and demonstrate performance improvement for each algorithm on both link prediction and attribute inference. Moreover, we make the novel observation that attribute inference can help inform link prediction, that is, link-prediction accuracy is further improved by first inferring missing attributes. We comprehensively evaluate these algorithms and compare them with other existing algorithms using a novel, large-scale Google+ dataset, which we make publicly available (http://www.cs.berkeley.edu/~stevgong/gplus.html). [ABSTRACT FROM AUTHOR]