Мы используем файлы cookies для улучшения работы сайта НИУ ВШЭ и большего удобства его использования. Более подробную информацию об использовании файлов cookies можно найти здесь, наши правила обработки персональных данных – здесь. Продолжая пользоваться сайтом, вы подтверждаете, что были проинформированы об использовании файлов cookies сайтом НИУ ВШЭ и согласны с нашими правилами обработки персональных данных. Вы можете отключить файлы cookies в настройках Вашего браузера.
The paper provides a review of distributed graph algorithms research conducted by authors. We consider an asynchronous distributed system model represented by a strongly connected directed rooted graph with bounded edge capacity (in a sense that only a bounded number of messages can be sent through an edge in a given time interval). A graph can be static or dynamic, i.e. changing. For a static graph we propose a spanning (in- and out-) tree construction algorithm of time complexity O(n/k+d)O(n/k+d), requiring O(ndlogΔ+)O(ndlogΔ+)message size and the same size of memory of each computing agent located in graph vertex, where nn is the number of vertices of the graph, kk is the capacity of an edge, dd is the maximum length of simple path in the graph, Δ+Δ+ is the maximum outdegree of the vertices. The spanning trees constructed can be used in distributed computation of a function of the multiset of values assigned to graph vertices in a time not greater than 3d3d. In a dynamic graph we suppose that k=1k=1 and an edge can appear, disappear, or change its end. We propose a dynamic graph monitoring algorithm than delivers information on any change to the root of the graph in O(n)O(n) or O(d)O(d) after the changes are stopped. We also propose graph exploration and marking algorithm with time complexity O(n)O(n). The marking provided by it is used in distributed computation of a function of the multiset of values assigned to dynamic graph vertices, which can be performed in time O(n2)O(n2)with messages of size O(logn)O(logn) or in time O(n)O(n) with messages of size O(nlogn)O(nlogn).
In this paper, we study the problem of learning graph embeddings for dynamic networks and the ability to generalize to unseen nodes called inductive learning. Firstly, we overview the state-of-the-art methods and techniques for constructing graph embeddings and learning algorithms for both transductive and inductive approaches. Secondly, we propose an improved GSM based on GraphSAGE algorithm and set up the experiments on datasets CORA, Reddit, and HSEcite, which is collected from Scopus citation database across the authors with affiliation to NRU HSE in 2011–2017. The results show that our three-layer model with attention-based aggregation function, added normalization layers, regularization (dropout) outperforms suggested by the respective authors’ GraphSAGE models with mean, LSTM, and pool aggregation functions, thus giving more insight into possible ways to improve inducting learning model based on GraphSAGE model.