Graphs are powerful combinatorial data structures that can model real-life data and the relationships among the entities inside the data. These graph models and representations are commonly used in a variety of domains, including social networks, recommender systems, and biological systems. Some say “if you torture the data long enough, they will confess”. With graphs, you do not need to be cruel. If you know how to use them, they will tell you a lot. As a part of the EuroCC project, we, researchers from the NCC Turkey, have organized a four-day Graph School to make people learn more about graphs, why to use them, and how to use them. This year, due to the COVID-19 pandemic, the school was online; however, a total of 120 participants attended the school.
On the first day of the school, Dr. Ezgi Karabulut Türkseven from Sabancı University gave a lecture on Graph Algorithms and introduced various search algorithms, with examples on the shortest path problem, the maximum flow problem, and the minimum cost flow problem. For each problem, the participants explored basic definitions, interesting application areas, and popular solutions with varying complexities.
On the second day, Dr. Onur Varol and Dr. Öznur Taştan from Sabancı University, gave two lectures on Network Science and Graph Embedding, respectively. In the morning session, Dr. Varol described network science concepts and motivated the audience to think in terms of networks when analyzing their data. Topological network measures such as centralities, density, and connectivity definitions were introduced. He also talked about random network models and their implications, as well as the mathematical properties of these graphs. Properties of different real-world networks discussed and implications of power-law degree distributions are introduced. Finally, the presentation described frequently used approaches in community detection and their applications.
Many machine learning applications, making predictions using graph-structured data, require a representation of the nodes and edges in a graph as a tabular feature list. In her lecture, Dr. Taştan focused on graph embedding and graph representation learning. The first part was focusing on classical graph node embedding methods, while the second part was an overview of knowledge graph representation learning. The lecture continued with two demo sessions covering examples of commonly used tools for this purpose, conducted by Ege Alpay and Amro Alabsi Aljundi.
One can model data samples observed on irregular domains such as energy, transportation, social, and sensor networks as graph signals: temperature measurements over a sensor network, or certain tendencies of users in a social network can be modelled as graph signals. In the morning session of the third day of our graph school, Dr. Elif Vural from Middle East Technical University first briefly overviewed the main concepts from spectral graph theory to make the students understand how frequency analysis techniques can be applied to graph signals. In the second part of the lecture, she discussed the extension of several classical/modern tools widely used in data science to signals on irregular graph domains; including transform-domain representations, sparse representations, neural networks, and stochastic processes.
Real-life graphs can be so large and have a streaming nature, such as social networks and postings, which make them hard to analyze by tools and libraries excelled for high-performance analysis of medium-scale, static graphs. In the second part of day three, Ahmet Demirelli from Sabancı University gave a lecture on how extremely large-scale graphs can be handled by using modern tools such as Spark GraphX. He covered the technical and practical aspects of using GraphX efficiently. The increase in the amount of graph data and the need for storing and analysing such data led to the development of Graph Databases. Additionally, representing text data in the form of graphs makes it possible to extract new and different types of information by representing the rich and complex relationships between different entities. In the first lecture of the last day, Dr. Pınar Karagöz from Middle East Technical University shared her experience in representing text as graphs, extracting information from these graphs, and the use of graph databases to store, access, and analyze them. Within this scope, Dr. Karagöz and Fırat Çekinel (Ph.D. student at METU CENG) also provided practical examples on how to create graph databases, writing queries on several sample databases including various graph structures as well as text graphs.
Graph Neural Networks (GNN) recently became very popular as a machine learning approach to leveraging graph data. They involve deep neural networks with topology-based convolutions which enable the exploitation of inherent graph structures as well as additional metadata containing vertex- and edge-based features. GNNs have many practical applications such as item recommendation, molecular property estimation, personalized medicine, etc. In the last lecture, Dr. Kamer Kaya from Sabancı University covered the theory and practice of GNNs with examples on citation networks, enzymes, etc. with PyTorch Geometric.
We are aiming to repeat the Graph School next year in 2022. If the pandemic allows, we will have physical, face-to-face lectures. If you are interested, stay tuned and continue to follow our web pages and social media channels: