Hi everyone,
The previous announcement had the wrong date and time, please find the
correct information below.
****DM-Meeting Spring 2017****
WHO: Xinfeng Xu and Sorour Amiri
WHEN: Monday, May 15, 2017, @ 4:00 pm
WHERE: Torg 3160 A
WHAT: Xinfeng and I will talk about the following two papers:
- Title: DeepCas: an End-to-end Predictor of Information Cascades(WWW2017)
Abstract: Information cascades, effectively facilitated by most social
network platforms, are recognized as a major factor in almost every social
success and disaster in these networks. Can cascades be predicted? While
many believe that they are inherently unpredictable, recent work has shown
that some key properties of information cascades, such as size, growth, and
shape, can be predicted by a machine learning algorithm that combines many
features. These predictors all depend on a bag of hand-crafting features to
represent the cascade network and the global network structure. Such
features, always carefully and sometimes mysteriously designed, are not
easy to extend or to generalize to a different platform or domain. Inspired
by the recent successes of deep learning in multiple data mining tasks, we
investigate whether an end-to-end deep learning approach could effectively
predict the future size of cascades. Such a method automatically learns the
representation of individual cascade graphs in the context of the global
network structure, without hand-crafted features and heuristics. We find
that node embeddings fall short of predictive power, and it is critical to
learn the representation of a cascade graph as a whole. We present
algorithms that learn the representation of cascade graphs in an end-to-end
manner, which significantly improve the performance of cascade prediction
over strong baselines that include feature based methods, node embedding
methods, and graph kernel methods. Our results also provide interesting
implications for cascade prediction in general.
- Title:Learning Combinatorial Optimization Algorithms over Graphs (arXive
2017)
Abstract: Many combinatorial optimization problems over graphs are
NP-hard, and require significant specialized knowledge and trial-and-error
to design good heuristics or approximation algorithms. Can we automate this
challenging and tedious process, and learn the algorithms instead? In many
real world applications, it is typically the case that the same type of
optimization problem is solved again and again on a regular basis,
maintaining the same problem structure but differing in the data. This
provides an opportunity for learning heuristic algorithms which can exploit
the structure of such recurring problems. In this paper, we propose a
unique combination of reinforcement learning and graph embedding to address
this challenge. The learned greedy policy behaves like a meta-algorithm
which incrementally constructs a solution, and the action is determined by
the output of a graph embedding network capturing the current state of the
solution. We show that our framework can be applied to a diverse range of
optimization problems over graphs, and provide evidence that our learning
approach can compete with or outperform specialized heuristics or
approximation algorithms for the Minimum Vertex Cover, Maximum Cut and
Traveling Salesman Problems.
Best regards,
Sorour
