Helsinki Algorithms Seminar: "Predicting Positive and Negative Links with Noisy Queries: Theory & Practice" Charalampos Tsourakakis

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design

Speaker:
Charalampos Tsourakakis

Title:
Predicting Positive and Negative Links with Noisy Queries: Theory & Practice

Abstract:
In this talk, I will present some recent results on an important graph mining problem known as the edge sign prediction problem: can we predict whether an interaction between a pair of nodes will be positive or negative? We model the edge sign prediction problem as follows: we are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability $0<q<\frac{1}{2}$. Let $\delta=1-2q$ be the bias. We provide an algorithm that recovers all signs correctly with high probability in the presence of noise for any constant gap $\delta$ with $O(\frac{n\log n}{\delta^4})$ queries. Our algorithm uses breadth first search as its main algorithmic primitive. A byproduct of our proposed learning algorithm is the use of $s-t$ paths as an informative feature to predict the sign of the edge $(s,t)$. As a heuristic, we use edge disjoint $s-t$ paths of short length as a feature for predicting edge signs in real-world signed networks. Our findings suggest that the use of paths improves the classification accuracy of state-of-the-art classifiers, especially for pairs of nodes with no or few common neighbors.

https://arxiv.org/abs/1709.07308

Joint work with Michael Mitzenmacher (Harvard), Jarosaw Basiok (Harvard), Ben Lawson (BU), Preetum Nakkiran (Harvard), Vasileios Nakos (Harvard).

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.