Abstract
Signed networks transform the information encoded by conventional graphs by attaching either a positive or a negative sign to every edge. This subtle modification vastly enhances the modelling capabilities of graphs. For instance, in a social network, where edges might represent interactions between users, the sign may determine whether an exchange was friendly or hostile. However, the introduction of edge signs invalidates many established methods and results from the graph-mining toolbox, and thus, problem formulations and algorithmic techniques must be studied anew. In this tutorial we aim to provide an overview of the literature in mining signed networks. We will present the most important theoretical results since their inception to the present day, we will discuss some of the most common applications, and we will reflect on emerging applications and directions for future work.
Outline
The tutorial will be divided into four sections: introduction, theory, problems & applications, and future directions.
- Introduction
- Motivation and applications
- Theory
- Balance theory. The interpretation of signs as indicative of friendship/enmity leads to balance theory. We will discuss basic concepts and present fundamental results.
- Spectral theory. The spectral theory of signed graphs is fundamentally different to that of their unsigned counterparts. We will define the signed Laplacian and discuss its properties. We will introduce the concept of switching equivalence and its implications.
- Frustration. If a graph is imbalanced, how much do we need to modify it so that it becomes balanced? This is the notion of frustration, which spurs some of the key questions in combinatorial optimization and graph mining in relation to signed networks.
- Problems and applications
- Subgraph mining
- Graph partitioning
- Correlation clustering
- Link prediction and classification
- Network dynamics
- Graph embedding and representation learning
- Future directions Research interest in signed networks has increased significantly over the last few years. We will discuss opportunities for further inquiry in the near future, covering some of the most compelling open problems and emerging applications.
Materials
Tutors
Aristides Gionis is a professor in KTH Royal Institute of Technology, an adjunct professor in Aalto University, and a research fellow in ISI Foundation. Previously he was a senior research scientist in Yahoo! Research. He received his PhD from Stanford University in 2003. He is currently serving as an associate editor in DMKD, TKDD, and TWEB. His research interests include data mining, web mining, and social-network analysis.
Antonis Matakos is a PhD student in the Data Mining Group of the Computer Science Department at Aalto University. He obtained his MSc degree from the University of Ioannina, Greece. His research interests belong broadly to the area of algorithmic data mining, with specific focus on social network analysis, graph theory and web mining. His PhD thesis project focuses on proposing social media models and algorithms for social good.
Bruno Ordozgoiti is a postdoctoral researcher for the Data Mining Group at the department of Computer Science in Aalto University. He earned a PhD in Computer Science from Universidad Politécnica de Madrid, Spain, in 2018. His research interests cover graph theory, graph mining and approximate matrix decompositions. His recent work covers polarized community detection in signed networks and algorithmic methods to tackle polarization in social media.
Han Xiao is currently a 4th year PhD student in the Data Mining group of Computer Science Department at Aalto University. He received his MSc degree from University of Helsinki, Finland. His research interests include data mining, combinatorial optimization, spectral graph theory and algorithmic fairness. Previously, he worked as Research Assistant at ISI foundation, Helsinki University, and Tongji University, as well as a Data Science Intern at Facebook, London.