Danai Koutra
University of Michigan, USA
DOOCN-XII: Network Representation Learning
Dynamics On and Of Complex Networks 2019
Frank Room of the UVM Davis Center
University of Vermont, Burlington, Vermont, USA
Tuesday, May 28th 2019 1:45pm–5:30pm
The Dynamics On and Of Complex Networks (DOOCN) workshop series, aims on exploring statistical dynamics on and of complex networks. Dynamics on networks refers to the different types of processes that take place on networks, like spreading, diffusion, and synchronization. Modeling such processes is strongly affected by the topology and temporal variation of the network structure, i.e., by the dynamics of networks. Recently, machine learning techniques have been used to model dynamics of massively large complex networks generated from big data, and the various functionalities resulting from the networks. This motivates us to focus on “Network Representation Learning” as the significant topic of interest in the 2019 edition.
Network Representation Learning or Graph Embedding is a technique that aims to compute vector space representations of nodes and edges of a network, that capture their relations semantically. Recently Network Representation Learning has seen a lot of research focus from the Network Science community for its ability to automatically capture different sorts of complex semantic relations between components of a graph without explicit programming.
The 12th edition of the DOOCN workshop, “DOOCN-XII: Network Representation Learning” will be held in conjunction with the upcoming NetSci 2019 conference, which will take place during 27–31 May 2019, in Burlington, Vermont, USA.
Invited Speakers
Program
- 13:45–13:55: Welcome and introductions by Dr. Parantapa Bhattacharya
- 13:55–14:30:
Invited Talk by Dr. Yuxiao Dong
Title: Representation learning on networks
Abstract: Over the past few years, representation learning has been offering a revolutionary paradigm for mining and learning with network data. In this talk, I will give a systematic introduction for this ongoing paradigm shift. I will start the talk with industry examples to explain how network analysis and graph mining on the Web are benefiting from representation learning, as well as its associated challenges. Then I will show how current developments on this problem can conceptually fall into three different categories, i.e., graph spectral, neural network, and matrix factorization based techniques. Importantly, I will demonstrate how these methods can be theoretically connected and unified with each other. For example, we find that skip-gram based network embedding methods are in essence implicitly factorizing matrices with closed forms, which are closely connected with the theory of graph Laplacian. Finally, I will show how we can leverage sparse matrix factorization for learning representations on large-scale networks. [Slides]
- 14:30–15:05:
Invited Talk by Prof. Danai Koutra
Title: Pocket-size structural embeddings in large-scale networks
Abstract: Networks naturally capture a host of real-world interactions, from social interactions and email communication to web browsing to brain activity. Over the past few years, representation learning over networks has been shown to be successful in a variety of downstream tasks, such as classification, link prediction, and visualization. Most existing approaches seek to learn node representations that capture node proximity. In this talk, I will discuss our recent work on a different class of node representations that aim to preserve the structural similarity between the nodes. I will present the lessons learned from designing efficient structural embedding methods for large-scale heterogeneous data, including ways to overcome the computational challenges and massive storage requirements that many existing techniques face. Throughout the talk, I will discuss applications to professional role discovery, entity resolution, entity linking across data sources, and more. [Slides]
- 15:05–15:20: Coffee Break
- 15:20–15:55:
Invited Talk by Prof. Manos Papagelis
Title: Fast and Accurate Mining of Evolving and Trajectory Networks
Abstract: Large-scale network mining and analysis is key to revealing the underlying dynamics of complex networks, not easily observable before. In this talk, I will present our recent work in mining specific types of dynamic networks. In the first part, I will present EvoNRL, a random-walk based method for effectively learning low-dimensional continuous representations of evolving networks. The key idea of our approach is to maintain a set of random walks that are consistent with the updates that occur in the network topology. That way we are able to learn a new mapping from the evolving network to a low-dimension network representation on-demand, with similar accuracy and at a fraction of the cost of traditional random-walk based network representation learning methods. In the second part, I will discuss our research on mining and analysis of large-scale trajectory networks - networks where the nodes are moving objects (cars, pedestrians, etc.) and the edges represent contacts between objects as defined by a proximity threshold. I will first motivate the problem of evaluating the importance of a moving object (node importance) in such networks; then I will present SLOT, a fast and exact method that can concurrently evaluate the importance of all moving objects (nodes) based on node degree, triangle membership and connected component network metrics, over time. [Slides]
- 15:55–16:30:
Invited Talk by Dr. Andres Abeliuk
Title: Friendship Paradox Biases Perceptions in Directed Networks
Abstract: How popular a topic or an opinion appears to be in a network can be very different from its actual popularity. For example, in an online network of a social media platform, the number of people who mention a topic in their posts---i.e., its global popularity---can be dramatically different from how people see it in their social feeds---i.e., its perceived popularity---where the feeds aggregate their friends' posts. We trace the origin of this discrepancy to the friendship paradox in directed networks, which states that people are less popular than their friends (or followers) are, on average. We identify conditions on network structure that give rise to this perception bias, and validate the findings empirically using data from Twitter. Within messages posted by Twitter users in our sample, we identify topics that appear more frequently within the users' social feeds, than they do globally, i.e., among all posts. In addition, we present a polling algorithm that leverages the friendship paradox to obtain a statistically efficient estimate of a topic's global prevalence from biased perceptions of individuals. We characterize the bias of the polling estimate, provide an upper bound for its variance, and validate the algorithm's efficiency through synthetic polling experiments on our Twitter data. Our paper elucidates the non-intuitive ways in which the structure of directed networks can distort social perceptions and resulting behaviors. [Slides]
- 16:30–17:05:
Invited Talk by Prof. William L. Hamilton
Title: Compositional Fairness Constraints for Graph Embeddings
Abstract: Learning high-quality node embeddings is a key building block for machine learning models that operate on graph data, such as social networks and recommender systems. However, existing graph embedding techniques are unable to cope with fairness constraints, e.g., ensuring that the learned representations do not correlate with certain attributes, such as age or gender. In this talk, I will introduce an adversarial framework to enforce fairness constraints on graph embeddings. Our approach is compositional---meaning that it can flexibly accommodate different combinations of fairness constraints during inference. For instance, in the context of social recommendations, our framework would allow one user to request that their recommendations are invariant to both their age and gender, while also allowing another user to request invariance to just their age. Experiments on standard knowledge graph and recommender system benchmarks highlight the utility of our proposed framework. [Slides]
- 17:05–17:30:
Panel discussion
Topic: The Future of Network Representation Learning
Moderator: Dr. Sandipan Sikdar
Panelists: Prof. Danai Koutra, Prof. Manos Papagelis, Dr. Yuxiao Dong, Prof. William L. Hamilton, and Dr. Andres Abeliuk
Organizers
History
The first Dynamics On and Of Complex Networks (DOOCN I) took place in Dresden, Germany, on 4th October 2007, as a satellite workshop of the European Conference on Complex Systems 07. The workshop received a large number of quality submissions from authors pursuing research in multiple disciplines, thus making the forum truly inter-disciplinary. There were around 20 speakers who spoke about the dynamics on and of different systems exhibiting a complex network structure, from biological systems, linguistic systems, and social systems to various technological systems like the Internet, WWW, and peer-to-peer systems. The organizing committee has published some of the very high quality original submissions as an edited volume from Birkhauser, Boston describing contemporary research position in complex networks.
After the success of DOOCN I, the organizers launched Dynamics On and Of Complex Networks – II (DOOCN II), a two days satellite workshop of the European Conference of Complex Systems 08. DOOCN II was held in Jerusalem, Israel, on the 18th and 19th September 2008.
DOOCN III was held as a satellite of ECCS 2009 in the University of Warwick, UK on 23rd and 24th of September. In continuation, DOOCN IV was held again as a satellite of ECCS 2010 in the University Institute Lisbon, Portugal on 16th September.
DOOCN V was held as a satellite of ECCS 2011 in the University of Vienna on 14th – 15th September 2011.
DOOCN VI took place in Barcelona, as a satellite to ECCS 2013, and focused on Semiotic Dynamics in time-varying social media. As DOOCN I, the other five DOOCN workshops counted with a large number participants and attracted prominent scientist in the field.
DOOCN VII, held in Lucca as a satellite to ECCS 2014, focused on Big Data aspects. DOOCN VIII was held in Zaragoza with focus also on BigData aspects.
The 9th edition of DOOCN was held in Amsterdam at Conference on Complex Systems (CCS) with the theme “Mining and learning for complex networks”.
The 2017 edition of DOOCN was held in Indianapolis USA in conjunction with NetSci 2017.
The 2018 edition of DOOCN XI was held in Thessaloniki, Greece at Conference on Complex Systems (CCS) with the theme “Machine learning for complex networks”.
DOOCN Book Series
The organizing committees of the DOOCN workshop series have published three Birkhäuser book volumes, from selected talks from the series.