Mine the node association: Dig into the essence of graphs

Yan, Yuchen

Permalink

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

Description

Title

Mine the node association: Dig into the essence of graphs

Author(s)

Yan, Yuchen

Issue Date

2025-02-13

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

Tong, Hanghang

Doctoral Committee Chair(s)

Tong, Hanghang

Committee Member(s)

• Han, Jiawei
• Abdelzaher, Tarek
• Perozzi, Bryan

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Graph neural networks
• Graph mining
• Network embedding

Abstract

In the era of big data, graph arises as a crucial data structure. Compared with other types of data, the essence of graphs large lies in node association, which represents unique, informative and important relation between nodes. Recently, mining the node association has attracted remarkable attentions in many high-impact domains, such as academic collaboration, e-commercial platform and infrastructure construction. Despite tremendous advances being achieved in mining the node association, three key challenges still exist. First (the association challenge), the meanings of node association are disparate, which refers to the fact that the node pair connected by the association could possess similar or opposite attributes (i.e., homophily vs. heterophily). Second (the model challenge), the goals and strategies of model design can be complicated. For example, competing sampling strategies exist in network embedding based algorithms (e.g., the distant positive sampling strategy, and close negative sampling strategy). Third (the graph challenge), almost any real graph keeps evolving. How to capture the evolution pattern of node association and predict future node association largely remain to be explored (static graph vs. dynamic graph). The theme of my Ph.D. research is to mine node associations. To deal with the above three challenges, we divide the node association mining problem into two dimensions: association type (homophily vs. heterophily) and graph type (static graph vs. dynamic graph). Based on these two dimensions, we present and discuss the design space of node association models, which includes 4 parts: (1) homophilic association mining in static graph; (2) homophilic association mining in dynamic graph; (3) heterophilic association mining in static graph; and (4) heterophilic association mining in dynamic graph. First, regarding homophilic association mining in static graph, we have reconciled the competing sampling strategies in existing network embedding methods and develop a novel network embedding model Sensei. Furthermore, for multi-network homophilic association mining, we bridge two categories of network alignment works and designe a network alignment algorithm BRIGHT. Second, for homophilic association mining in dynamic graphs, we propose the first dynamic knowledge graph alignment algorithm DiNGAl. In addition, we design a family of algorithms ,FITO to decouple the within-layer association from cross-layer association in both static and dynamic setting. Third, for heterophilic association mining in static graph, we study this problem from two angles. For one thing, we try to enable graph convolutional networks (GCN) to automatically detect the heterophily in graphs and develop a GCN with trainable depth named TeDGCN. Based on TeDGCN, we further propose a more scalable inductive GNN model SloG. For another, we study the relation between positional node association and structural node association and our proposed model PaCEr can generate structural node embeddings from positional node embeddings. Moreover, we design a more powerful structural embedding algorithm TAWE, which generates better embeddings for structural node association tasks. At last, for heterophilic association mining in dynamic graph, we propose the formal definition of temporal heterophily and design a temporal heterophilic graph convolutional network THeGCN.

Graduation Semester

2025-05

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2024 Yuchen Yan

Owning Collections