Empowering graph intelligence via natural and artificial dynamics

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Fu, Dongqi

Contributors dc:contributor

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

• Graph Deep Learning
• Graph Machine Learning
• Graph Data Mining
• Graph Ai

Statement dc:rights

• Copyright 2024 Dongqi Fu

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F125571