An Evolution Kernel Method for Graph Classification through Heat Diffusion Dynamics

• URL: http://arxiv.org/abs/2306.14688v1
• Date: Mon, 26 Jun 2023 13:32:11 GMT
• Title: An Evolution Kernel Method for Graph Classification through Heat Diffusion Dynamics
• Authors: Xue Liu, Dan Sun, Wei Wei, Zhiming Zheng
• Abstract summary: We propose a heat-driven method to transform each static graph into a sequence of temporal ones. This approach effectively describes the evolutional behaviours of the system. It has been successfully applied to classification problems in real-world structural graph datasets.
• Score: 12.094047128690834
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Autonomous individuals establish a structural complex system through pairwise connections and interactions. Notably, the evolution reflects the dynamic nature of each complex system since it recodes a series of temporal changes from the past, the present into the future. Different systems follow distinct evolutionary trajectories, which can serve as distinguishing traits for system classification. However, modeling a complex system's evolution is challenging for the graph model because the graph is typically a snapshot of the static status of a system, and thereby hard to manifest the long-term evolutionary traits of a system entirely. To address this challenge, we suggest utilizing a heat-driven method to generate temporal graph augmentation. This approach incorporates the physics-based heat kernel and DropNode technique to transform each static graph into a sequence of temporal ones. This approach effectively describes the evolutional behaviours of the system, including the retention or disappearance of elements at each time point based on the distributed heat on each node. Additionally, we propose a dynamic time-wrapping distance GDTW to quantitatively measure the distance between pairwise evolutionary systems through optimal matching. The resulting approach, called the Evolution Kernel method, has been successfully applied to classification problems in real-world structural graph datasets. The results yield significant improvements in supervised classification accuracy over a series of baseline methods.

Related papers

• Graph Neural Flows for Unveiling Systemic Interactions Among Irregularly Sampled Time Series [5.460420960898444]
  We develop a graph-based model that unveils the systemic interactions of time series observed at irregular time points. We validate our approach on several tasks, including time series classification and forecasting, to demonstrate its efficacy.
  arXiv  Detail & Related papers  (2024-10-17T21:10:39Z)
• Advancing Graph Generation through Beta Diffusion [49.49740940068255]
  Graph Beta Diffusion (GBD) is a generative model specifically designed to handle the diverse nature of graph data. We propose a modulation technique that enhances the realism of generated graphs by stabilizing critical graph topology.
  arXiv  Detail & Related papers  (2024-06-13T17:42:57Z)
• TimeGraphs: Graph-based Temporal Reasoning [64.18083371645956]
  TimeGraphs is a novel approach that characterizes dynamic interactions as a hierarchical temporal graph. Our approach models the interactions using a compact graph-based representation, enabling adaptive reasoning across diverse time scales. We evaluate TimeGraphs on multiple datasets with complex, dynamic agent interactions, including a football simulator, the Resistance game, and the MOMA human activity dataset.
  arXiv  Detail & Related papers  (2024-01-06T06:26:49Z)
• TransformerG2G: Adaptive time-stepping for learning temporal graph embeddings using transformers [2.2120851074630177]
  We develop a graph embedding model with uncertainty quantification, TransformerG2G, to learn temporal dynamics of temporal graphs. Our experiments demonstrate that the proposed TransformerG2G model outperforms conventional multi-step methods. By examining the attention weights, we can uncover temporal dependencies, identify influential elements, and gain insights into the complex interactions within the graph structure.
  arXiv  Detail & Related papers  (2023-07-05T18:34:22Z)
• Learning Dynamic Graph Embeddings with Neural Controlled Differential Equations [21.936437653875245]
  This paper focuses on representation learning for dynamic graphs with temporal interactions. We propose a generic differential model for dynamic graphs that characterises the continuously dynamic evolution of node embedding trajectories. Our framework exhibits several desirable characteristics, including the ability to express dynamics on evolving graphs without integration by segments.
  arXiv  Detail & Related papers  (2023-02-22T12:59:38Z)
• Time-aware Dynamic Graph Embedding for Asynchronous Structural Evolution [60.695162101159134]
  Existing works merely view a dynamic graph as a sequence of changes. We formulate dynamic graphs as temporal edge sequences associated with joining time of. vertex and timespan of edges. A time-aware Transformer is proposed to embed. vertex' dynamic connections and ToEs into the learned. vertex representations.
  arXiv  Detail & Related papers  (2022-07-01T15:32:56Z)
• Learning the Evolutionary and Multi-scale Graph Structure for Multivariate Time Series Forecasting [50.901984244738806]
  We show how to model the evolutionary and multi-scale interactions of time series. In particular, we first provide a hierarchical graph structure cooperated with the dilated convolution to capture the scale-specific correlations. A unified neural network is provided to integrate the components above to get the final prediction.
  arXiv  Detail & Related papers  (2022-06-28T08:11:12Z)
• Complex Evolutional Pattern Learning for Temporal Knowledge Graph Reasoning [60.94357727688448]
  TKG reasoning aims to predict potential facts in the future given the historical KG sequences. The evolutional patterns are complex in two aspects, length-diversity and time-variability. We propose a new model, called Complex Evolutional Network (CEN), which uses a length-aware Convolutional Neural Network (CNN) to handle evolutional patterns of different lengths.
  arXiv  Detail & Related papers  (2022-03-15T11:02:55Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• Learning Attribute-Structure Co-Evolutions in Dynamic Graphs [28.848851822725933]
  We present a novel framework called CoEvoGNN for modeling dynamic attributed graph sequence. It preserves the impact of earlier graphs on the current graph by embedding generation through the sequence. It has a temporal self-attention mechanism to model long-range dependencies in the evolution.
  arXiv  Detail & Related papers  (2020-07-25T20:07:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.