https://www.dagstuhl.de/21352

August 29 – September 1 , 2021, Dagstuhl Seminar 21352

Higher-Order Graph Models: From Theoretical Foundations to Machine Learning

Organizers

Tina Eliassi-Rad (Northeastern University – Boston, US)
Vito Latora (Queen Mary University of London, GB)
Martin Rosvall (University of Umeå, SE)
Ingo Scholtes (Universität Würzburg, DE)

For support, please contact

Jutka Gasiorowski for administrative matters

Michael Gerke for scientific matters

Dagstuhl Reports

As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.

Documents

List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule [pdf]

(Use personal credentials as created in DOOR to log in)

Motivation

Graph and network models are a cornerstone of data science and machine learning applications in computer science, social sciences, humanities, and life sciences. Most state-of-the-art network analysis and graph-based learning techniques build on simple graph abstractions, where nodes represent a system's elements, and links represent dyadic interactions, relations, or dependencies between those elements. This mathematical formalism has proven useful for reasoning about, for example, the centrality of nodes, the evolution and control of dynamical processes, and the community or cluster structure in complex systems.

While the advantages of graph models of relational data are undisputed, we often have access to rich data with multiple types of higher-order, inherently non-dyadic interactions that simple graphs cannot represent in a meaningful way. Important examples include relational data on actors in social systems who engage in group collaborations, time-stamped interaction data giving rise to chronologically ordered sequences of (dyadic) links, sequential data such as user clickstreams, mobility trajectories or citation paths with sequences of traversed nodes, and data on networked systems with multiple types or layers of connectivity. Over the past years, researchers have shown that the presence of such higher-order interactions can fundamentally influence our understanding of complex networked systems. They can change our notion of the importance of nodes captured by centrality measures, affect the detection of cluster and community structures in graphs, and influence dynamical processes like diffusion or epidemic spreading, as well as associated control or containment strategies in non-trivial ways.

To address this important challenge, researchers in topological data analysis, network science, machine learning, and physics recently started to generalize network analysis to higher-order graph models that capture more than dyadic relations. Over the past few years, this research community has developed a rich portfolio of higher-order network models and representations. Exemplary modelling approaches successfully use hypergraphs, simplicial network models, high-dimensional De Bruijn graphs, higher-, variable-, and multi-order Markov chains, as well as multi-layer and multiplex networks. These modelling approaches address the same fundamental limitation of graph models, namely that we cannot understand the structure and dynamics of complex systems by decomposing direct and indirect interactions between elements into a set of dyadic relations with a single type. However, the similarities and differences between these different modelling approaches, and the machine learning techniques derived from them, are poorly understood.

Addressing this gap, this Dagstuhl Seminar aims to improve our understanding of the strengths, weaknesses, commonalities, and differences of these different approaches along with their resulting computational challenges. Bringing together key researchers from different communities, the seminar aims to form a common foundation for the developing graph mining and machine learning techniques that use recent advances in the study of higher-order graph models. We specifically aim to develop a common language and a shared research platform that fosters progress in data analytics and machine learning for data with complex relational structure.

Motivation text license
  Creative Commons BY 3.0 DE
  Tina Eliassi-Rad, Vito Latora, Martin Rosvall, and Ingo Scholtes

Classification

  • Data Structures And Algorithms
  • Machine Learning
  • Social And Information Networks

Keywords

  • Topological data analysis
  • (social) network analysis
  • Graph theory
  • Statistical relational learning
  • Graph mining

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.