Auswahl der wissenschaftlichen Literatur zum Thema „Graph dynamics“

Dynamics always exist in complex systems. Graphs (complex networks) are a mathematical form for describing a complex system abstractly. Dynamics can be learned efficiently from the structure and dynamics state of a graph. Learning the dynamics in graphs plays an important role in predicting and controlling complex systems. Most of the methods for learning dynamics in graphs run slowly in large graphs. The complexity of the large graph’s structure and its nonlinear dynamics aggravate this problem. To overcome these difficulties, we propose a general framework with two novel methods in this paper, the Dynamics-METIS (D-METIS) and the Partitioned Graph Neural Dynamics Learner (PGNDL). The general framework combines D-METIS and PGNDL to perform tasks for large graphs. D-METIS is a new algorithm that can partition a large graph into multiple subgraphs. D-METIS innovatively considers the dynamic changes in the graph. PGNDL is a new parallel model that consists of ordinary differential equation systems and graph neural networks (GNNs). It can quickly learn the dynamics of subgraphs in parallel. In this framework, D-METIS provides PGNDL with partitioned subgraphs, and PGNDL can solve the tasks of interpolation and extrapolation prediction. We exhibit the universality and superiority of our framework on four kinds of graphs with three kinds of dynamics through an experiment.

Recent years have seen a surge in research on dynamic graph representation learning, which aims to model temporal graphs that are dynamic and evolving constantly over time. However, current work typically models graph dynamics with recurrent neural networks (RNNs), making them suffer seriously from computation and memory overheads on large temporal graphs. So far, scalability of dynamic graph representation learning on large temporal graphs remains one of the major challenges. In this paper, we present a scalable framework, namely SpikeNet, to efficiently capture the temporal and structural patterns of temporal graphs. We explore a new direction in that we can capture the evolving dynamics of temporal graphs with spiking neural networks (SNNs) instead of RNNs. As a low-power alternative to RNNs, SNNs explicitly model graph dynamics as spike trains of neuron populations and enable spike-based propagation in an efficient way. Experiments on three large real-world temporal graph datasets demonstrate that SpikeNet outperforms strong baselines on the temporal node classification task with lower computational costs. Particularly, SpikeNet generalizes to a large temporal graph (2.7M nodes and 13.9M edges) with significantly fewer parameters and computation overheads.

Many real-world networks evolve over time, which results in dynamic graphs such as human mobility networks and brain networks. Usually, the “dynamics on graphs” (e.g., node attribute values evolving) are observable, and may be related to and indicative of the underlying “dynamics of graphs” (e.g., evolving of the graph topology). Traditional RNN-based methods are not adaptive or scalable for learn- ing the unknown mappings between two types of dynamic graph data. This study presents a AD-ESN, and adaptive echo state network that can automatically learn the best neural net- work architecture for certain data while keeping the efficiency advantage of echo state networks. We show that AD-ESN can successfully discover the underlying pre-defined map- ping function and unknown nonlinear map-ping between time series and graphs.

In this paper, we study the necessary and sufficient time to explore constantly connected dynamics graphs by a mobile entity (agent). A dynamic graph is constantly connected if for each time units, there exists a stable connected spanning tree [10]. We focus on the case where the underlying graph is a cactus-path (graph reduced to a path of k rings in which two neighbor rings have at most one vertex in common) and we assume that the agent knows the dynamics of the graph. We show that 5n - Θ(1) time units are necessary and sufficient to explore any constantly connected dynamic graph based on the cactus-path 〖Ch〗_(2,n) (composed of two same size ringsn). The upper bound is generalized on dynamic graphs based on cacti-paths with k rings. We show that for any constantly connected dynamic graph of size N based on a cactus-path, 4N -max{n_1,n_k} -3k -3 time units are sufficient to explore the graph, with k the length of the path, N=∑_(i=1)^k▒n_i -k+1 the size of the dynamic graph and n_i the size of the ring which is at position i starting from left to right.

Graph dynamics for a node-labeled graph is a set of updating rules describing how the labels of each node in the graph change in time as a function of the global set of labels. The underpopulation rule is graph dynamics derived by simplifying the set of rules constituting the Game of Life. It is known that the number of label configurations met by a graph during the dynamic process defined by such rule is bounded by a polynomial in the size of the graph if the graph is undirected. As a consequence, predicting the labels evolution is an easy problem (i.e., a problem in P) in such a case. In this paper, the generalization of the underpopulation rule to signed and directed graphs is studied. It is here proved that the number of label configurations met by a graph during the dynamic process defined by any so generalized underpopulation rule is still bounded by a polynomial in the size of the graph if the graph is undirected and structurally balanced, while it is not bounded by any polynomial in the size of the graph if the graph is directed although unsigned unless P = PSpace.

In this paper, we study the necessary and sufficient time to explore with return constantly connected dynamic networks modelled by a dynamic graphs. Exploration with return consists, for an agent operating in a dynamic graph, of visiting all the vertices of the graph and returning to the starting vertex. We show that for constantly connected dynamic graphs based on a ring of sizen,3n-4 time units are necessary and sufficient to explore it. Assuming that the agent knows the dynamics of the graph.

For a graph G and a unary graph operation X, there is a graph sequence \G_k generated by G_0=G and G_{k+1}=X(G_k). Let Sp({G_k}) denote the set of normalized Laplacian eigenvalues of G_k. The set of limit points of \bigcup_{k=0}^\infty Sp(G_k)$, $\liminf_{k\rightarrow\infty}Sp(G_k) and $\limsup_{k\rightarrow \infty}Sp(G_k)$ are considered in this paper for graph sequences generated by two operations: subdivision and triangle extension. It is obtained that the spectral dynamic of graph sequence generated by subdivision is determined by a quadratic function, which is closely related to the the well-known logistic map; while that generated by triangle extension is determined by a linear function. By using the knowledge of dynamic system, the spectral dynamics of graph sequences generated by these two operations are characterized. For example, it is found that, for any initial non-trivial graph $G$, chaos takes place in the spectral dynamics of iterated subdivision graphs, and the set of limit points is the entire closed interval [0,2].

Modeling continuous-time dynamics constitutes a foundational challenge, and uncovering inter-component correlations within complex systems holds promise for enhancing the efficacy of dynamic modeling. The prevailing approach of integrating graph neural networks with ordinary differential equations has demonstrated promising performance. However, they disregard the crucial signed information potential on graphs, impeding their capacity to accurately capture real-world phenomena and leading to subpar outcomes. In response, we introduce a novel approach: a signed graph neural ordinary differential equation, adeptly addressing the limitations of miscapturing signed information. Our proposed solution boasts both flexibility and efficiency. To substantiate its effectiveness, we seamlessly integrate our devised strategies into three preeminent graph-based dynamic modeling frameworks: graph neural ordinary differential equations, graph neural controlled differential equations, and graph recurrent neural networks. Rigorous assessments encompass three intricate dynamic scenarios from physics and biology, as well as scrutiny across four authentic real-world traffic datasets. Remarkably outperforming the trio of baselines, empirical results underscore the substantial performance enhancements facilitated by our proposed approach. Our code can be found at https://github.com/beautyonce/SGODE.

The limitations of existing continuum bond graph modeling techniques have effectively precluded their use in large order problems, where nonrepetitive graph structures and causal patterns are normally present. As a result, despite extensive publication of bond graph models for continuous systems simulations, bond graph methods have not offered a viable alternative to finite element analysis for the vast majority of practical problems. However, a new modeling approach combining Lagrangian (mass fixed) bond graphs with a selected finite element discretization scheme allows for direct simulation of a wide range of large order solid continuum dynamics problems. With appropriate modifications, including the use of Eulerian (space fixed) bond graphs, the method may be extended to include fluid dynamics modeling.

Current graph-embedding methods mainly focus on static homogeneous graphs, where the entity type is the same and the topology is fixed. However, in real networks, such as academic networks and shopping networks, there are typically various types of nodes and temporal interactions. The dynamical and heterogeneous components of graphs in general contain abundant information. Currently, most studies on dynamic graphs do not sufficiently consider the heterogeneity of the network in question, and hence the semantic information of the interactions between heterogeneous nodes is missing in the graph embeddings. On the other hand, the overall size of the network tends to accumulate over time, and its growth rate can reflect the ability of the entire network to generate interactions of heterogeneous nodes; therefore, we developed a graph dynamics model to model the evolution of graph dynamics. Moreover, the temporal properties of nodes regularly affect the generation of temporal interaction events with which they are connected. Thus, we developed a node dynamics model to model the evolution of node connectivity. In this paper, we propose DHGEEP, a dynamic heterogeneous graph-embedding method based on the Hawkes process, to predict the evolution of dynamic heterogeneous networks. The model considers the generation of temporal events as an effect of historical events, introduces the Hawkes process to simulate this evolution, and then captures semantic and structural information based on the meta-paths of temporal heterogeneous nodes. Finally, the graph-level dynamics of the network and the node-level dynamics of each node are integrated into the DHGEEP framework. The embeddings of the nodes are automatically obtained by minimizing the value of the loss function. Experiments were conducted on three downstream tasks, static link prediction, temporal event prediction for homogeneous nodes, and temporal event prediction for heterogeneous nodes, on three datasets. Experimental results show that DHGEEP achieves excellent performance in these tasks. In the most significant task, temporal event prediction of heterogeneous nodes, the values of precision@2 and recall@2 can reach 30.23% and 10.48% on the AMiner dataset, and reach 4.56% and 1.61% on the DBLP dataset, so that our method is more accurate at predicting future temporal events than the baseline.