Directed Acyclic Graph Structure Learning from Dynamic Graphs
- URL: http://arxiv.org/abs/2211.17029v2
- Date: Tue, 5 Mar 2024 14:57:30 GMT
- Title: Directed Acyclic Graph Structure Learning from Dynamic Graphs
- Authors: Shaohua Fan, Shuyang Zhang, Xiao Wang, Chuan Shi
- Abstract summary: Estimating the structure of directed acyclic graphs (DAGs) of features (variables) plays a vital role in revealing the latent data generation process.
We study the learning problem of node feature generation mechanism on such ubiquitous dynamic graph data.
- Score: 44.21230819336437
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Estimating the structure of directed acyclic graphs (DAGs) of features
(variables) plays a vital role in revealing the latent data generation process
and providing causal insights in various applications. Although there have been
many studies on structure learning with various types of data, the structure
learning on the dynamic graph has not been explored yet, and thus we study the
learning problem of node feature generation mechanism on such ubiquitous
dynamic graph data. In a dynamic graph, we propose to simultaneously estimate
contemporaneous relationships and time-lagged interaction relationships between
the node features. These two kinds of relationships form a DAG, which could
effectively characterize the feature generation process in a concise way. To
learn such a DAG, we cast the learning problem as a continuous score-based
optimization problem, which consists of a differentiable score function to
measure the validity of the learned DAGs and a smooth acyclicity constraint to
ensure the acyclicity of the learned DAGs. These two components are translated
into an unconstraint augmented Lagrangian objective which could be minimized by
mature continuous optimization techniques. The resulting algorithm, named
GraphNOTEARS, outperforms baselines on simulated data across a wide range of
settings that may encounter in real-world applications. We also apply the
proposed approach on two dynamic graphs constructed from the real-world Yelp
dataset, demonstrating our method could learn the connections between node
features, which conforms with the domain knowledge.
Related papers
- GraphEdit: Large Language Models for Graph Structure Learning [62.618818029177355]
Graph Structure Learning (GSL) focuses on capturing intrinsic dependencies and interactions among nodes in graph-structured data.
Existing GSL methods heavily depend on explicit graph structural information as supervision signals.
We propose GraphEdit, an approach that leverages large language models (LLMs) to learn complex node relationships in graph-structured data.
arXiv Detail & Related papers (2024-02-23T08:29:42Z) - Homophily-enhanced Structure Learning for Graph Clustering [19.586401211161846]
Graph structure learning allows refining the input graph by adding missing links and removing spurious connections.
Previous endeavors in graph structure learning have predominantly centered around supervised settings.
We propose a novel method called textbfhomophily-enhanced structure textbflearning for graph clustering (HoLe)
arXiv Detail & Related papers (2023-08-10T02:53:30Z) - Learning from Heterogeneity: A Dynamic Learning Framework for Hypergraphs [22.64740740462169]
We propose a hypergraph learning framework named LFH that is capable of dynamic hyperedge construction and attentive embedding update.
To evaluate the effectiveness of our proposed framework, we conduct comprehensive experiments on several popular datasets.
arXiv Detail & Related papers (2023-07-07T06:26:44Z) - Dynamic Graph Representation Learning via Edge Temporal States Modeling and Structure-reinforced Transformer [5.093187534912688]
We introduce the Recurrent Structure-reinforced Graph Transformer (RSGT), a novel framework for dynamic graph representation learning.
RSGT captures temporal node representations encoding both graph topology and evolving dynamics through a recurrent learning paradigm.
We show RSGT's superior performance in discrete dynamic graph representation learning, consistently outperforming existing methods in dynamic link prediction tasks.
arXiv Detail & Related papers (2023-04-20T04:12:50Z) - GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
Graph Influence Function (GIF) is a model-agnostic unlearning method that can efficiently and accurately estimate parameter changes in response to a $epsilon$-mass perturbation in deleted data.
We conduct extensive experiments on four representative GNN models and three benchmark datasets to justify GIF's superiority in terms of unlearning efficacy, model utility, and unlearning efficiency.
arXiv Detail & Related papers (2023-04-06T03:02:54Z) - Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance.
Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
arXiv Detail & Related papers (2022-01-17T11:57:29Z) - Dynamic Graph Learning-Neural Network for Multivariate Time Series
Modeling [2.3022070933226217]
We propose a novel framework, namely static- and dynamic-graph learning-neural network (GL)
The model acquires static and dynamic graph matrices from data to model long-term and short-term patterns respectively.
It achieves state-of-the-art performance on almost all datasets.
arXiv Detail & Related papers (2021-12-06T08:19:15Z) - Dynamic Graph Representation Learning via Graph Transformer Networks [41.570839291138114]
We propose a Transformer-based dynamic graph learning method named Dynamic Graph Transformer (DGT)
DGT has spatial-temporal encoding to effectively learn graph topology and capture implicit links.
We show that DGT presents superior performance compared with several state-of-the-art baselines.
arXiv Detail & Related papers (2021-11-19T21:44:23Z) - DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints.
We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly.
We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
arXiv Detail & Related papers (2021-06-14T07:11:36Z) - Tensor Graph Convolutional Networks for Multi-relational and Robust
Learning [74.05478502080658]
This paper introduces a tensor-graph convolutional network (TGCN) for scalable semi-supervised learning (SSL) from data associated with a collection of graphs, that are represented by a tensor.
The proposed architecture achieves markedly improved performance relative to standard GCNs, copes with state-of-the-art adversarial attacks, and leads to remarkable SSL performance over protein-to-protein interaction networks.
arXiv Detail & Related papers (2020-03-15T02:33:21Z)
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.