Enterprise AI Analysis

Problem Formulation in Dynamic Graph Learning

The dynamic graph system is denoted as G = {G(1), G(2), . . ., G(T) }, where each time step t corresponds to a graph structure G(t) = (v(t), E(t)). Here, v(t) = {U1, U2, ..., Un} represents the set of nodes involved in interactions at time t, and E(t) = {lij | Vi, Vj ∈ V(t)} records the connection relationships between nodes at time t. The graph topology evolves over time, with the elements and size of V(t) and E(t) potentially changing. Accordingly, the system includes a sequence of adjacency matrices A = {A(1), A(2), ..., A (t)}, where each A(t) ∈ {0,1}N(*) ×N(t) is defined such that A = 1 if and only if eij ∈ E(t). The node feature sequence is denoted as X = {X(1), X(2), ..., X(t)}, where X(t) ∈ RN(t)×d contains the feature vectors of all nodes, with each node vi having a feature vector xt) ∈ R1xd. Here, N(t) refers to the number of nodes at time step t, and d is the dimensionality of the feature vector for each node. For the graph neural network model, the input data at each time step is represented by the adjacency matrix and node features, i.e., D(t) = (A(t), x(t)).

Graph Condensation Strategy

The condensing process first generates the node set of the condensed graph based on the distribution ratio of node labels. Given the original graph G = (V, E), the node set of the condensed graph V' is generated proportionally according to the frequency of each label in the node set. The generation of the edge set E' in the condensed graph depends on the similarity measure between nodes. For any two nodes v and v', the presence of an edge between them depends on their similarity. If the similarity sij between the nodes exceeds a predefined threshold 0, an edge is considered to exist between the nodes. The similarity sij is computed by: Sij = sim(v, v) = |||||||| Finally, the condensed graph can be represented as G' = (V', E'), where the edge set E' is formed by the following rule: E' = {(v'i, v'j, Sij) | Sij ≥ 0} Here, @ is the similarity threshold, used to ensure that only edges with higher similarity are retained. Our approach utilizes CGC for graph condensation. Unlike methods reliant on gradient matching or bi-level optimization, CGC introduces a training-free paradigm that transforms the objective into a class-to-node distribution matching problem. This is efficiently solved as a class partition task using clustering algorithms to generate condensed node features.

Historical Graph Embeddings Generation

To replay information from the condensed historical graph to the model, we generate historical graph embeddings using a training approach with multiple condensed graphs. We feed a series of condensed graphs into a dynamic graph model and extract embeddings from the final condensed graph's features, with the methodology formalized as follows: Let {G.G.....,GT)} represent the sequence of condensed historical graphs. Each condensed graph can be represented as G = (Vt),E,X). Taking EvolveGCN [84] as an example, for the sequence {G®,G,...,GT)}, GT), the model parameters @ are updated at each time step t as follows: 0(t) = GRU(0(t-1), $(G))), t = 1, 2, ...,T where: 0(t) represents the updated model parameters at time step t, ((t-1) denotes the parameters from the previous time step, $(GC) is a feature extraction function that extracts features from the condensed graph (Gt)), GRU is the Gated Recurrent Unit used to update parameters based on current graph features and previous parameters.Through this sequential training process, the model parameters @ gradually adapt to the evolutionary patterns in the condensed graph sequence. After training completion, the historical graph embeddings are generated using the final parameters (0(T) and the last condensed graph, expressed as fe(T) (V(GT)))."

Concatenation of Historical and Current Embeddings

To effectively integrate historical knowledge with current graph structural information, we propose an embedding fusion method based on feature dimension concatenation. Let Hcurrent ∈ Rn×dn represent the current node embeddings generated by the graph neural network, where n denotes the number of nodes and dn represents the node embedding dimension. The historical embeddings Hhistorical ∈ Rn×dh_are extracted from the final condensed graph using the trained dynamic graph model: Hhistorical = fo(T) (V(GT))) By performing concatenation along the feature dimension, the two embedding representations are fused into a unified feature representation: Hcombined = Concat(Hcurrent, Hhistorical) ∈ Rn×(dn+dh) To address the node matching problem between the current graph and the condensed historical graph, a cosine similarity-based threshold method is adopted: if the similarity between a current node and any node of condensed historical graph exceeds the threshold, their representations are concatenated; otherwise, zero-padding is applied. The resulting embeddings Hcombined can be directly used for downstream tasks. This approach enables the model to simultaneously leverage structural patterns learned from historical graph data and specific features of the current graph.

Selective Historical Replay Mechanism

To address the issue that indiscriminate historical information replay can negatively impact nodes minimally affected by structural changes, we introduce a selective replay mechanism that confines historical embedding concatenation to significantly affected nodes. Our approach first detects structural changes by comparing the current and previous graphs to identify added/removed nodes and edges. The influence region is then defined as k-hop subgraphs centered around nodes directly connected to these topological modifications, as shown in Figure 2. Historical embeddings are selectively concatenated only for nodes within this identified change region, aiming for effective knowledge transfer while maintaining model accuracy. The formal definition is: Rchange = U {u ∈ V₁ | d(u, v) ≤ k} VES where S denotes nodes adjacent to topological modifications and d(u, v) represents the shortest path distance in Gt. Historical embeddings are exclusively concatenated for nodes within Rchange.