Empowering graph intelligence via natural and artificial dynamics

Fu, Dongqi

Permalink

https://hdl.handle.net/2142/125571 Copy

Description

Title

Empowering graph intelligence via natural and artificial dynamics

Author(s)

Fu, Dongqi

Issue Date

2024-07-08

Director of Research (if dissertation) or Advisor (if thesis)

He, Jingrui

Doctoral Committee Chair(s)

He, Jingrui

Committee Member(s)

• Abdelzaher, Tarek
• Han, Jiawei
• Maciejewski, Ross

Department of Study

Siebel Computing &DataScience

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Graph Deep Learning
• Graph Machine Learning
• Graph Data Mining
• Graph AI

Abstract

In the era of big data, the relationship between entities has become much more complex than ever before. As a kind of relational data structure, graph attracts much research attention for dealing with this unprecedented phenomenon. The real-world scenarios usually bring two fundamental and pragmatic challenges to graph research. First, the graph structure and features may be complex over time (i.e., time-evolving topological structures, time-evolving node/graph features/labels, etc.). Without proper time information leverage, the resulting problems include but are not limited to ignoring entity temporal correlation, overlooking causality discovery, computation inefficiency, non-generalization, etc. Second, the initial topological structure and node or graph features may be imperfect (e.g., having construction errors, sampling noises, missing features, scarce labels, hard-to-interpret, redundant, privacy-leaking, robustness-lacking, etc.). The corresponding problems include but are not limited to non-robustness, indiscriminative representations, and non-generalization. Inspired by the above two kinds of problems, my research focuses on natural dynamics and artificial dynamics for graphs. Natural dynamics can be illustrated as disentangling the spatial-temporal complexity of input graphs with evolving components, e.g., the topology structures and (sub)graph-level features are dependent on time. As for artificial dynamics in graphs, this concept describes how researchers change the existing or construct the non-existing graph-related elements, e.g., graph topology, node/graph attributes, graph neural network (GNN) layer connections, and GNN gradients. In general, studying natural dynamics and artificial dynamics is investigating how to leverage spatial-temporal properties of graphs and augment and prune graph components to upgrade graph-based AI performance in terms of effectiveness, efficiency, trustworthiness, etc. In this thesis, we propose to build the algorithmic foundation for the next-generation graph AI development with three main pillars, i.e., natural dynamics of graphs, artificial dynamics of graphs, and \natural + artificial dynamics of graphs. For example, to name a few, (1) we first finished a literature review for the natural and artificial dynamics of graphs in terms of concept, progress, and future; (2) by studying natural dynamics, we developed more accurate graph classification and more efficient graph alignment algorithms; (3) by studying artificial dynamics, we have developed the explainable node and graph classification algorithms and a powerful graph neural computational framework; (4) by studying natural + artificial dynamics, we obtained efficient algorithms for high-order graph clustering and partitioning algorithms.

Graduation Semester

2024-08

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/125571

Copyright and License Information

Copyright 2024 Dongqi Fu

Owning Collections