%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Thu1A: Social Network Mining II}{Francesco Bonchi}{Chem,  LT1}
\timeTitlePeople{10:30--10:55}{On Approximation of Real-World Influence Spread}{Yu Yang, Enhong Chen, Qi Liu, Biao Xiang, Tong Xu and Shafqat Ali Shad}

\abst{To find the most influential nodes for viral marketing, several
models have been proposed to describe the influence propagation
process. Among them, the \textit{Independent Cascade~(IC) Model} is
most widely-studied. However, under IC model, computing influence
spread~(i.e., the expected number of nodes that will be influenced)
for each given seed set has been proved to be \#P-hard. To that
end, in this paper, we propose \textit{GS} algorithm for quick approximation of
influence spread by solving a linear system, based on the fact that
propagation probabilities in real-world social networks are usually
quite small. Furthermore, for better approximation, we study the
structural defect problem existing in networks, and correspondingly,
propose enhanced algorithms, \textit{GSbyStep} and \textit{SSSbyStep}, by incorporating the
\textit{Maximum Influence Path} heuristic. Our algorithms are
evaluated by extensive experiments on four social networks.
Experimental results show that our algorithms can get better
approximations to the IC model than the state-of-the-arts.}


\timeTitlePeople{10:55--11:20}{Opinion Formation by Voter Model with Temporal Decay Dynamics
}{Masahiro Kimura, Kazumi Saito, Kouzou Ohara and Hiroshi Motoda}

\abst{Social networks play an important role for spreading information and
forming opinions. A variety of voter models have been defined that help
analyze how people make decisions based on their neighbors' decisions. In
these studies, common practice has been to use the latest decisions in
opinion formation process. However, people may decide their opinions by
taking account not only of their neighbors' latest opinions, but also of
their neighbors' past opinions. To incorporate this effect, we enhance
the original voter model and define the temporal decay voter (TDV) model
incorporating a temporary decay function with parameters, and propose an
efficient method of learning these parameters from the observed opinion
diffusion data. We further propose an efficient method of selecting the
most appropriate decay function from among the candidate functions each
with the optimized parameter values. We adopt three functions as the
typical candidates: the exponential decay, the power-law decay, and no
decay, and evaluate the proposed method (parameter learning and model
selection) through extensive experiments.  We, first, experimentally
demonstrate, by using synthetic data, the effectiveness of the proposed
method, and then we analyze the real opinion diffusion data from a
Japanese word-of-mouth communication site for cosmetics using three
decay functions above, and show that most opinions conform to the TDV
model of the power-law decay function.}


\timeTitlePeople{11:20--11:45}{Viral Marketing for Product Cross-Sell through Social Networks}{Ramasuri Narayanam and Amit A.\ Nanavati}

\abst{The well known {\em influence maximization problem} (or viral marketing through social networks) deals with selecting a few influential initial seeds
to maximize the awareness of product(s) over the social network. In this paper, we introduce a novel and generalized version of the influence maximization problem
that considers simultaneously the following three practical aspects: (i) Often cross-sell among products is possible, (ii) Product specific costs (and benefits) for promoting the products have to be considered, and (iii) Since a company often has budget constraints, the initial seeds have to be chosen within a given budget. We refer to this generalized problem setting as {\em Budgeted Influence Maximization with Cross-sell of Products (B-IMCP)}.
To the best of our knowledge, we are not aware of any work in the literature that addresses the B-IMCP problem which is the subject matter of this paper.
Given a fixed budget, one of the key issues associated with the B-IMCP problem is to choose the initial seeds within this budget not only for the individual products, but also for promoting cross-sell phenomenon among these products. In particular, the following are the specific contributions of this paper: (i) We propose an influence propagation model to capture both the cross-sell phenomenon and product specific costs and benefits; (ii) As the B-IMCP problem is NP-hard computationally, we present a simple greedy approximation algorithm and then derive the approximation guarantee of this greedy algorithm by drawing upon the results from the theory of matroids; (iii) We then outline two efficient heuristics based on well known concepts in the literature. Finally, we experimentally evaluate the proposed approach for the B-IMCP problem using a few well known social network data sets such as WikiVote data set, Epinions, and Telecom call detail records data.}


\timeTitlePeople{11:45--12:10}{Which Topic will You Follow?}{Deqing Yang, Yanghua Xiao, Bo Xu, Hanghang Tong, Wei Wang and Sheng Huang}

\abst{Who are the most appropriate candidates to receive a call-for-paper or call-for-participation? What session topics should we propose for a conference of next year? To answer these questions, we need to precisely predict research topics of authors. In this paper, we build a MLR (Multiple Logistic Regression) model to predict the topic-following behavior of an author.
By empirical studies, we find that social influence and homophily are two fundamental driving forces of topic diffusion in SCN (Scientific Collaboration Network). Hence, we build the model upon the explanatory variables representing above two driving forces. Extensive experimental results show that our model can consistently achieves good predicting performance. Such
results are independent of the tested topics and significantly better than that of state-of-the-art competitor.}


\sessionend

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Thu1B: Rule Learning and Subgroup Discovery}{Eyke H\"{u}llermeier}{Chem, LT2}
\timeTitlePeople{10:30--10:55}{A Bayesian Approach for Classification Rule Mining in Quantitative Databases}{Dominique Gay and Marc Boull\'{e}} 

\abst{We suggest a new framework for classification rule mining in quantitative data sets founded on Bayes theory -- without univariate preprocessing of attributes. We introduce a space of rule models and a prior distribution defined on this model space. As a result, we obtain the definition of a parameter-free criterion for classification rules. We show that the new criterion identifies interesting classification rules while being highly resilient to spurious patterns. We develop a new parameter-free algorithm to mine locally optimal classification rules efficiently. The mined rules are directly used as new features in a classification process based on a selective naive Bayes classifier. The resulting classifier demonstrates higher inductive performance than state-of-the-art rule-based classifiers.}


\timeTitlePeople{10:55--11:20}{A Bayesian Scoring Technique for Mining Predictive and Non-Spurious Rules
}{Iyad Batal, Gregory Cooper and Milos Hauskrecht}

\abst{Rule mining is an important class of data mining methods for discovering interesting patterns in data. The success of a rule mining method heavily depends on the evaluation function that is used to assess the quality of the rules. In this work, we propose a new rule evaluation score - the Predictive and Non-Spurious Rules (PNSR) score. This score relies on Bayesian inference to evaluate the quality of the rules and considers the structure of the rules to filter out spurious rules. We present an efficient algorithm for finding rules with high PNSR scores. The experiments demonstrate that our method is able to cover and explain the data with a much smaller rule set than existing methods.}


\timeTitlePeople{11:20--11:45}{Generic Pattern Trees for Exhaustive Exceptional Model Mining
}{Florian Lemmerich, Martin Becker and Martin Atzmueller}

\abst{Exceptional model mining has been proposed as a variant of subgroup discovery especially focusing on complex target concepts.
Currently, efficient mining algorithms are limited to heuristic (non exhaustive) methods.
In this paper, we propose a novel approach for fast exhaustive exceptional model mining:
We introduce the concept of valuation bases as an intermediate condensed data representation, and present the general GP-growth algorithm based on FP-growth.
Furthermore, we discuss the scope of the proposed approach by drawing an analogy to data stream mining and provide examples for several different model classes.
Runtime experiments show improvements of more than an order of magnitude in comparison to a naive exhaustive depth-first search. }


\timeTitlePeople{11:45--12:10}{Handling Time Changing Data with Adaptive Very Fast Decision Rules}{Petr Kosina and Jo\~{a}o Gama}

\abst{Data streams are usually characterized by changes in the underlying
distribution generating data. Therefore algorithms designed to work
with data streams should be able to detect changes and quickly adapt
the decision model. Rules are one of the most interpretable and
flexible models for data mining prediction tasks. In this paper we
present the Adaptive Very Fast Decision Rules (\texttt{AVFDR}), an on-line, any-time and one-pass algorithm for learning decision rules in the context of time changing data. \texttt{AVFDR} can learn ordered and unordered rule sets. It is able to adapt the decision model via incremental induction and specialization of rules.
Detecting local drifts takes advantage of the modularity of rule sets.
In \texttt{AVFDR}, each individual rule monitors the evolution of performance metrics to detect concept drift. \texttt{AVFDR} prunes rules that detect drift.
This explicit change detection mechanism provides useful information about the dynamics of the process generating data, faster adaption to changes and generates compact rule sets.
The experimental evaluation shows this method is able to learn fast and compact rule sets from evolving streams in comparison to alternative methods.}


\sessionend

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\sessionHeader{Thu1C: Multi-Task and Transfer Learning I}{George Forman}{Chem, LT3}
\timeTitlePeople{10:30--10:55}{Efficient Training of Graph-Regularized Multitask SVMs
}{Christian Widmer, Marius Kloft, Nico G\"{o}rnitz and Gunnar R\"{a}tsch}

\abst{We present an optimization framework for graph-regularized multi-task SVMs based on the \emph{primal} formulation of the problem. Previous approaches employ a so-called multi-task kernel (MTK) and thus are inapplicable when the numbers of training examples $n$ is large (typically $n<20,000$, even for just a few tasks). In this paper, we present a primal optimization criterion, allowing for general loss functions, and derive its dual representation. Building on the work of Hsieh et al., we derive an algorithm for optimizing the large-margin objective and prove its convergence.  Our computational experiments show a speedup of up to \emph{three orders of magnitude} over LibSVM and SVMLight for several standard benchmarks as well as challenging data sets from the application domain of computational biology. Combining our optimization methodology with the COFFIN large-scale learning framework, we are able to train a multi-task SVM using over 1,000,000 training points stemming from 4 different tasks. An efficient C++ implementation of our algorithm is being made publicly available as a part of the SHOGUN machine learning toolbox.}


\timeTitlePeople{10:55--11:20}{Geometry Preserving Multi-task Metric Learning
}{Peipei Yang, Kaizhu Huang and Cheng-Lin Liu}

\abst{Multi-task learning has been widely studied in machine learning due to its capability to improve the performance of multiple related learning problems. However, few researchers have applied it on the important metric learning problem. In this paper, we propose to couple multiple related metric learning tasks with von Neumann divergence. On one hand, the novel regularized approach extends previous methods from the vector regularization to a general matrix regularization framework; on the other hand and more importantly, by exploiting von Neumann divergence as the regularizer, the new multi-task metric learning has the capability to well preserve the data geometry. This leads to more appropriate propagation of side-information among tasks and provides potential for further improving the performance. We propose the concept of \emph{geometry preserving probability~(PG)} and show that our framework leads to a larger PG in theory. In addition, our formulation proves to be jointly convex and the global optimal solution can be guaranteed. A series of experiments across very different disciplines verify that our proposed algorithm can consistently outperform the current methods.}


\timeTitlePeople{11:20--11:45}{Learning and Inference in Probabilistic Classifier Chains with Beam Search
}{Abhishek Kumar, Shankar Vembu, Aditya Krishna Menon and Charles Elkan}

\abst{Multilabel learning is an extension of binary classification that is both challenging and practically important. Recently, a method for multilabel learning called \emph{probabilistic classifier chains} (PCCs) was proposed with numerous appealing properties, such as conceptual simplicity, flexibility, and theoretical justification. However, PCCs suffer from the \emph{computational} issue of having inference that is exponential in the number of tags, and the \emph{practical} issue of being sensitive to the suitable ordering of the tags while training. In this paper, we show how the classical technique of \emph{beam search} may be used to solve both these problems. Specifically, we show how to use beam search to perform tractable test time inference, and how to integrate beam search with training to determine a suitable tag ordering. Experimental results on a range of multilabel datasets show that these proposed changes dramatically extend the practical viability of PCCs.}


\timeTitlePeople{11:45--12:10}{Learning Multiple Tasks with Boosted Decision Trees
}{Jean Baptiste Faddoul, Boris Chidlovskii, R\'{e}mi Gilleron and Fabien Torre}

\abst{We address the problem of multi-task learning %, and more specifically multi-task classification 
with no label correspondence among tasks. Learning multiple related tasks simultaneously, by exploiting their shared knowledge 
can improve the predictive performance on every task. 
%However, prior art works made some convenience assumptions to cope with multi-task problems. Most critical ones are assuming that the tasks share the same labels and /
%or examples, and they follow the same relatedness pattern across the whole learning space.
%In this work, we propose a novel technique for the multi-task learning with no label correspondence among tasks. 
We develop the multi-task Adaboost environment with Multi-Task Decision Trees as weak classifiers. 
We first adapt the well known decision tree learning to the multi-task setting. 
%Decision trees are naturally multi-class classifiers, thus Multi-Task Decision Trees can learn multiple multi-class classification tasks. 
We revise the information gain rule for learning decision trees in the multi-task setting. We use this feature to develop a novel criterion for learning Multi-Task Decision
Trees. The criterion guides the tree construction by learning the decision rules from data of different tasks, and representing different degrees of task relatedness. 
We then modify MT-Adaboost to combine Multi-task Decision Trees as weak learners. We experimentally validate the advantage of the new technique; we report results of experiments conducted on several multi-task datasets, including the Enron email set and Spam Filtering collection.
}
\sessionend

