Машинное обучение на графах

Преподаватель: Сальников Всеволод Николаевич

Модуль: 3

Кредиты: 2

Аннотация:

Графы представляют собой весьма удобную структуру данных, так как с одной стороны позволяют моделировать весьма разнообразные процессы (тезис “Everything can be a network”), с другой - абстрагироваться от ненужных деталей, тем самым поднимая эффективность. Целью данного курса является демонстрация текущих возможностей по работе с графами, с точки зрения анализа данных. По результатам прохождения курса, студенты освоят как ощутимый теоретический базис, на котором строятся современные подходы работы с сетями, так и практические методы, применяемые в реальных приложениях. Даже классические методы машинного обучения зачастую можно улучшить, привнеся туда характеристики, извлеченные из соответствующих графов.

Помимо набора упражнений, которые будут предлагаться на лекциях для самостоятельного изучения, основная практическая работа представляет из себя выполнение творческого проекта (в группах по 3 студента) по применению навыков, изученных за время курса, на конкретных данных.

План занятий:

Mathematical toolbox

    A. Probability

    B. Renewal processes

    C. Random walks and diffusion

    D. Distributions

    E. Maximum likelihood

    F. Entropy, information and similarity measures

    G. Matrix algebra

    H. Markov chains

    I. Branching processes

Basic structural properties of networks

    A. Definitions

    B. Degree distribution

    C. Measures derived from walks and paths

    D. Clustering coefficient

    E. Centralities

    F. Spectral properties

Models of networks

    A. Erdos-Renyi random graph

    B. Configuration model

    C. Network motifs

    D. Growing network with preferential

    attachment

Community detection

    A. Graph partitioning

    B. Modularity

    C. Spectral optimization of modularity

    D. Louvain method

    E. Limitations of modularity optimisation

Dynamics, time-scales and Communities

    A. Notations

    B. Consensus dynamics

    C. Time-scale separation in dynamical systems and networks

    D. Dynamically invariant subspaces and external equitable partitions in networks

Dynamics: Random walks

    A. Discrete-time random walks on networks

    B. Application: PageRank

    C. Mean first-passage and recurrence times

    D. Application: Respondent-driven sampling

    E. Continuous-Time Random Walks

Random walks to reveal network structure

    A. Markov stability

    B. Infomap

    C. Walktrap

    D. Core–periphery structure

    E. Similarity measures and kernels

Epidemic processes

    A. Models of epidemic processes

    B. SIS dynamics on metapopulation models

    C. Discrete-State Dynamics

Embeddings and Graph neural networks / Graph convolutional networks

Applications

Требования:

С точки зрения программирования, предполагаются базовые навыки. Конкретный язык программирования не фиксируется, но, ввиду наличия широкого спектра библиотек, знание python упрощает жизнь, поэтому в > 90% случаев студенты используют именно его. Примеры, рассматриваемые во время курса, тоже демонстрируются на нём. Учитывая, что графы - весьма математический объект, то в курсе довольно много вещей рассматриваются относительно глубоко с математической точки зрения. В начале курса предусмотрен экскурс в необходимые математические аспекты, в зависимости от уровня аудитории, он может быть короче или длиннее. Желательно уверенное понимание теории вероятностей и матричной алгебры, так как эти аспекты используются постоянно.

Для кого: студенты 3-4 курсов ПМИ и 1-2 курсов МОВС

Расписание: четверг 19:00 с 20 января онлайн