%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Wed2A: Social Network Mining I}{Jan Ramon}{Chem, LT1}
\timeTitlePeople{14:00--14:25}{Discovering Links among Social Networks}{Francesco Buccafurri, Gianluca Lax, Antonino Nocera, and Domenico Ursino} 

\abst{Distinct social networks are interconnected via bridge users,
who play thus a key role when crossing information is investigated in
the context of Social Internetworking analysis.
Unfortunately, not always users make
their role of {\em bridge} explicit by specifying the so-called {\tt me} edge (i.e., the edge connecting the accounts of the same
user in two distinct social networks), missing thus a potentially very useful
information. As a consequence, discovering missing {\tt me} edges is an important problem to face in this
context yet not so far investigated.
In this paper, we propose a common-neighbors approach to detecting
missing {\tt me} edges, which returns good results in real life settings.
Indeed, an
experimental campaign shows both that the state-of-the-art
common-neighbors approaches cannot be effectively applied to our problem
and, conversely, that our approach returns precise and complete results.}


\timeTitlePeople{14:25--14:50}{Efficient Bi-objective Team Formation in Social Networks}{Mehdi Kargar Aijun An, and Morteza Zihayat} 

\abst{We tackle the problem of finding a team of experts from a social
network to complete a project that requires a set of skills. The
social network is modeled as a graph. A node in the graph
represents an expert and has a weight representing the monetary
cost for using the expert service. Two nodes in the graph can be
connected and the weight on the edge represents the communication
cost between the two corresponding experts. Given a project, our
objective is to find a team of experts that covers all
the required skills and also minimizes the communication cost as
well as the personnel cost of the project. To minimize both of
the objectives, we define a new combined cost function which is
based on the linear combination of the objectives (i.e.\
communication and personnel costs). We show that the problem of
minimizing the combined cost function is an NP-hard problem. Thus,
one approximation algorithm is proposed to solve the problem. The
proposed approximation algorithm is bounded and the approximation
ratio of the algorithm is proved in the paper. Three heuristic
algorithms based on different intuitions are also proposed for
solving the problem. Extensive experiments on real datasets
demonstrate the effectiveness and scalability of the proposed
algorithms.
}


\timeTitlePeople{14:50--15:15}{Feature-Enhanced Probabilistic Models for Diffusion Network Inference}{Liaoruo Wang, Stefano Ermon and John E.\ Hopcroft} 

\abst{Cascading processes, such as disease contagion, viral marketing, and information diffusion, are a pervasive phenomenon in many types of networks. The problem of devising intervention strategies to facilitate or inhibit such processes has recently received considerable attention. However, a major challenge is that the underlying network is often unknown. In this paper, we revisit the problem of inferring latent network structure given observations from a diffusion process, such as the spread of trending topics in social media. We define a family of novel probabilistic models that can explain recurrent cascading behavior, and take into account not only the time differences between events but also a richer set of additional features. We show that MAP inference is tractable and can therefore scale to very large real-world networks. Further, we demonstrate the effectiveness of our approach by inferring the underlying network structure of a subset of the popular Twitter following network by analyzing the topics of a large number of messages posted by users over a 10-month period. Experimental results show that our models accurately recover the links of the Twitter network, and significantly improve the performance over previous models based entirely on time.}


\timeTitlePeople{15:15--15:40}{Influence Spread in Large-Scale Social Networks -- A Belief Propagation Approach}{Huy Nguyen and Rong Zheng} 

\abst{Influence maximization is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under a certain diffusion model. The Greedy algorithm for influence maximization first proposed by Kempe, later improved by Leskovec suffers from two sources of computational deficiency: 1) the need to evaluate many candidate nodes before selecting a new seed in each round, and 2) the calculation of the influence spread of any seed set relies on Monte-Carlo simulations. In this work, we tackle both problems by devising efficient algorithms to compute influence spread and determine the best candidate for seed selection. The fundamental insight behind the proposed algorithms is the linkage between influence spread determination and belief propagation on a directed acyclic graph (DAG). Experiments using real-world social network graphs with scales ranging from thousands to millions of edges demonstrate the superior performance of the proposed algorithms with moderate computation costs.}


\sessionend

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Wed2B: Large-Scale, Distributed and Parallel Mining and Learning I}{Yizhao Ni}{Chem, LT2}
\timeTitlePeople{14:00--14:25}{Learning Compact Class Codes for Fast Inference in Large Multi Class Classification}{M. Ciss\'{e}, T. Arti\`{e}res and Patrick Gallinari} 

\abst{We describe a new approach for classification with a very large number of classes where we assume some class similarity information is available, e.g.\ through a hierarchical organization. The proposed method learns a compact binary code using such an existing similarity information defined on classes. Binary classifiers are then trained using this code and decoding is performed using a simple nearest neighbor rule. This strategy, related to Error Correcting Output Codes methods, is shown to perform similarly or better than the standard and efficient one-vs-all approach, with much lower inference complexity.}


\timeTitlePeople{14:25--14:50}{ParCube: Sparse Parallelizable Tensor Decompositions}{Evangelos E.\ Papalexakis, Christos Faloutsos and Nicholas D.\ Sidiropoulos} 

\abst{How can we efficiently decompose a tensor into sparse factors, when the data does not fit in memory? 
Tensor decompositions have gained a steadily increasing popularity in data mining applications, however 
the current state-of-art decomposition algorithms operate on main memory and do not scale to truly large datasets.
In this work, we propose ParCube, a new and highly parallelizable method for speeding up tensor 
decompositions that is well-suited to producing sparse approximations. Experiments with even moderately large 
data indicate over 90\% sparser outputs and 14 times faster execution, with  approximation error close to the current state of the art 
irrespective of computation and memory requirements. We provide theoretical guarantees for the algorithm's correctness and we 
experimentally validate our claims through extensive experiments, including four different real world datasets (ENRON, LBNL, FACEBOOK and NELL), 
demonstrating its effectiveness for data mining practitioners. In particular, we are the first to analyze the very large 
NELL dataset using a sparse tensor decomposition,
%was unable to be analyzed through current state of the art tools,
demonstrating that ParCube enables us to handle effectively and efficiently very large datasets.}


\timeTitlePeople{14:50--15:15}{Stochastic Coordinate Descent Methods for Regularized Smooth and Nonsmooth Losses}{Qing Tao, Kang Kong, Dejun Chu and Gaowei Wu} 

\abst{Stochastic Coordinate Descent (SCD) methods are among the first optimization schemes suggested for efficiently solving large scale problems. However, until now, there exists a gap between the convergence rate analysis and practical SCD algorithms for general smooth losses and there is no primal SCD algorithm for nonsmooth losses. In this paper, we discuss these issues using the recently developed structural optimization techniques. In particular, we first present a principled and practical SCD algorithm for regularized smooth losses, in which the one-variable subproblem is solved using the proximal gradient method and the adaptive componentwise Lipschitz constant is obtained employing the line search strategy. When the loss is nonsmooth, we present a novel SCD algorithm, in which the one-variable subproblem is solved using the dual averaging method. We show that our algorithms exploit the regularization structure and achieve several optimal convergence rates that are standard in the literature. The experiments demonstrate the expected efficiency of our SCD algorithms in both smooth and nonsmooth cases.}


\timeTitlePeople{15:15--15:40}{Sublinear Algorithms for Penalized Logistic Regression in Massive Datasets}{Haoruo Peng, Zhengyu Wang, Edward Y.\ Chang, Shuchang Zhou and Zhihua Zhang} 

\abst{Penalized logistic regression (PLR) is a widely used supervised learning model.
In this paper, we consider its applications in large-scale data problems and resort to a stochastic primal-dual approach for solving PLR.
In particular, we employ a random sampling technique in the primal step and a multiplicative weights method in the dual step.
This technique leads to an optimization method with sublinear dependency on both the volume and dimensionality of training data.
We develop concrete algorithms for PLR with $\ell_2$-norm and $\ell_1$-norm penalties, respectively.
Experimental results over several large-scale and high-dimensional datasets demonstrate both efficiency and accuracy of our algorithms.}


\sessionend

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Wed2C: Online Learning and Data Streams}{Jo\~{a}o Gama}{Chem, LT3}
\timeTitlePeople{14:00--14:25}{Adaptive Two-View Online Learning for Math Topic Classification}{Tam T.\ Nguyen, Kuiyu Chang and Siu Cheung Hui} 

\abst{Text categorization has been a popular research topic for years and has become more or less a practical technology. However, there exists little research on math topic classification. Math documents contain both textual data and math expressions. The text and math can be considered as two related but different views of a math document. The goal of online math topic classification is to automatically categorize a math document containing both mathematical expressions and textual content into an appropriate topic without the need for periodically retraining the classifier. To achieve this, it is essential to have a two-view online classification algorithm, which deals with the textual data view and the math expression view at the same time. In this paper, we propose a novel adaptive two-view online math document classifier based on the Passive Aggressive (PA) algorithm. The proposed approach is evaluated on real world math questions and answers from the Math Overflow question answering system. Compared to the baseline PA algorithm, our method's overall F-measure is improved by up to 3\%. The improvement of our algorithm over the plain math expression view is almost 6\%.}


\timeTitlePeople{14:25--14:50}{BDUOL: Double Updating Online Learning on a Fixed Budget}{Peilin Zhao and Steven C.H.\ Hoi} 

\abst{Kernel-based online learning often exhibits promising empirical performance for various applications according to previous studies. However, it often suffers a main shortcoming, that is, the unbounded number of support vectors, making it unsuitable for handling large-scale datasets. In this paper, we investigate the problem of budget kernel-based online learning that aims to constrain the number of support vectors by a predefined budget when learning the kernel-based prediction function in the online learning process. Unlike the existing studies, we present a new framework of budget kernel-based online learning based on a recently proposed online learning method called ``Double Updating Online Learning" (DUOL), which has shown state-of-the-art performance as compared with the other traditional kernel-based online learning algorithms. We analyze the theoretical underpinning of the proposed Budget Double Updating Online Learning (BDUOL) framework, and then propose several BDUOL algorithms by designing different budget maintenance strategies. We evaluate the empirical performance of the proposed BDUOL algorithms by comparing them with several well-known budget kernel-based online learning algorithms, in which encouraging results validate the efficacy of the proposed technique.}


\timeTitlePeople{14:50--15:15}{Improved Counter Based Algorithms for Frequent Pairs Mining in Transactional Data Streams}{Konstantin Kutzkov} 

\abst{A straightforward approach to frequent pairs mining in transactional streams is to generate all pairs occurring in  transactions and apply a frequent items mining algorithm to the resulting stream. The well-known counter based algorithms {\sc Frequent} and {\sc Space-Saving} are known to achieve a very good approximation when the frequencies of the items in the stream adhere to a skewed distribution.

Motivated by observations on real datasets, we present a general technique for applying {\sc Frequent} and {\sc Space-Saving} to transactional data streams for the case when the transactions considerably vary in their lengths. Despite of its simplicity, we show through extensive experiments that our approach is considerably more efficient and precise than the na\"ive application of {\sc Frequent} and {\sc Space-Saving}.}


\timeTitlePeople{15:15--15:40}{Mirror Descent for Metric Learning: A Unified Approach}{Gautam Kunapuli and Jude Shavlik} 

\abst{Most metric learning methods are characterized by diverse loss
functions and projection methods, which naturally begs the question:
is there a wider framework that can generalize many of these
methods? In addition, ever persistent issues are those of
scalability to large data sets and the question of kernelizability.
We propose a unified approach to Mahalanobis metric learning: an
online regularized metric learning algorithm based on the ideas of
composite objective mirror descent (\textsc{comid}). The metric
learning problem is formulated as a regularized positive
semi-definite matrix learning problem, whose update rules can be
derived using the {\sc comid} framework. This approach aims to be
scalable, kernelizable, and admissible to many different types of
Bregman and loss functions, which allows for the tailoring of
several different classes of algorithms. The most novel contribution
is the use of the trace norm, which yields a sparse metric in its
eigenspectrum, thus simultaneously performing feature selection
along with metric learning.}


\sessionend


