[Audio] Hello, everyone. I am Zhi xiang Shen, a senior undergraduate student from the University of Electronic Science and Technology of China. Today, I will be presenting our paper accepted at NeurIPS 2024, titled 'Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning.' This research was conducted by Zhi xiang Shen, Shuo Wang, and Zhao Kang from the University of Electronic Science and Technology of China. You can find the link to our paper and the code via the QR codes shown on the slide.. 

Scene 1

Advances in Neural Information Processing Systems (NeurIPS), 2024

Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning

1University of Electronic Science and Technology of China

[Audio] Let's start with an introduction to multiplex graphs. A multiplex graph is a special type of multi-relational heterogeneous graph with multiple layers spanning a common set of nodes. These graphs are particularly useful because they provide richer information and better modeling capabilities compared to single-layer graphs. Our focus is on Unsupervised Multiplex Graph Learning, which aims to learn node representations by leveraging diverse graph structures and features without manual labeling. This approach is crucial for applications where labeled data is scarce or unavailable. Unsupervised Multiplex Graph Learning has various applications, including biological network analysis, social network mining, and recommendation systems.. 

Scene 2

A special type of multi-relational heterogeneous graph with multiple graph layers span across a common set of nodes.

Unsupervised Multiplex Graph Learning (UMGL): Learn node representations by leveraging diverse graph structures and features without manual labeling.
 Applications： Biological Network Analysis, Social Network Mining, Recommendation Systems......

[1] Jing B, Park C, Tong H. Hdmi: High-order deep multiplex infomax. Proceedings of the Web Conference (WWW), 2021.
 [2] Qian X, Li B, Kang Z. Upper Bounding Barlow Twins: A Novel Filter for Multi-Relational Clustering. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2024.

[Audio] However, there are overlooked aspects in UMGL. First, the reliability of the graph structure can be compromised by task-irrelevant information such as irrelevant, heterophilic, and missing edges. This noise can significantly degrade the performance of graph learning algorithms. Therefore, beyond graph-fixed methods need to be explored to adapt to real-world noisy data. Second, there is the issue of multiplex graph non-redundancy, where task-relevant information exists not only in shared information between graphs but also within the unique information of certain graphs. In multiplex graph data, shared task-relevant information can manifest as homophilic edges common to all graphs, while unique task-relevant information is reflected in homophilic edges that appear only in a specific graph. This means that simply focusing on shared information can lead to the loss of valuable insights.. 

Scene 3

❖ Overlooked Aspects of Unsupervised Multiplex Graph Learning

1) The reliability of graph structure  · Task-irrelevant information:     irrelevant, heterophilic, and missing edges                   beyond graph-fixed methods
 2) Multiplex graph non-redundancy · Shared task-relevant information:     homophilic edges common to all graphs · Unique task-relevant information:     homophilic edges appear only in a certain graph

Graph I
Shared relevant edge
Unique relevant edge I

[Audio] Based on the above observations, we first theoretically define Multiplex Graph Non-redundancy from the perspective of mutual information. Two graph structures are non-redundant with respect to label information if and only if the conditional mutual information is strictly greater than zero. We further conducted empirical analyses on real multiplex graph datasets. The related tables show the unique relevant edge ratio in each graph, which measures the graph-unique task-relevant information. It can be observed that non-redundancy is widespread in real data, highlighting the limitations of existing methods that only capture shared information.. 

Scene 4

Definition 1. Gi is considered non-redundant with Gj for Y if and only if there exists € > 0 such
that the conditional mutual information I (Gt; Y I G)) > € or I Y I Gt) > €.

Multiplex Graph Non-redundancy: Task-relevant information exists not only in the shared information between graphs but also potentially within the unique information of certain graphs.

Dataset
ACM
DBLP
Yelp
MAG
Nodes
3,025
2,957
2,614
113,919
Relation type
Paper-Author-Paper (PA P)
Paper-Subject-Paper (PSP)
Author-Paper-Author (APA)
Author-Paper-Conference-Paper-A uthor (APCPA)
msiness-User-Business (BUB)
Business-Service-Business (BSB)
Business-Rating Levels-Business (BLB)
Paper-Paper (PP)
Paper-Author-Paper (PA P)
Edges
26,416
2,197,556
2,398
525,718
1,484,692
Unique relevant
edge ratio (%)
38.08
99.05
99.82
83.12
97.49
93.07
64.59
93.48

[Audio] We define our research problem from the perspective of graph structure learning. The goal is to learn a fused graph from the original multiplex graph in an unsupervised manner, mitigating task-irrelevant noise while retaining sufficient task-relevant information. This is achieved by refining the graph structure to remove irrelevant edges and by ensuring that both shared and unique task-relevant information are preserved.. 

Scene 5

❖ Problem Definition · Graph Structure Learning (GSL) Perspective:

How can we learn a fused graph from the original multiplex graph in an unsupervised manner, mitigating task-irrelevant noise while retaining sufficient task-relevant information?

[Audio] We propose an Information-aware Unsupervised Multiplex Graph Fusion method. Our approach takes the original multiplex structures and node features as input without requiring label information, and outputs the learned structure and node representations. First, we remove irrelevant noise from each graph view. Meanwhile, we maximize both shared and unique task-relevant information for each graph. To capture unique task-relevant information in an unsupervised manner, we propose a learnable generative graph augmentation. Finally, the entire optimization process is performed using a differentiable lower/upper bound of the mutual information, ensuring an accurate estimation of mutual information.. 

Scene 6

Multiplex Graph Graph Structure Refinement
Task-relevant Information Maximizing
GI
Graph
Learner
Optimal
Graph Aug.
Refined Graph
Fused Graph
Refined Graph
Optimal
Graph Aug.
Shared
Graph
Encoder
Update
: Parameters
Maximize Mutual
Information
'Downstream Node Classification
Node Clustering
Tasks
Unique Task-
relevant Information
Shared Task-
relevant Information
Graph Fusion

❖ Information-aware Unsupervised Multiplex Graph Fusion

Input: Multiplex Structures, Node Features
 Output: Learned Structure, Representations
 · Removing irrelevant noise by GSL
 · Maximizing both shared and unique task-    relevant information for each graph
 · Learnable generative graph augmentation
 · Optimization using differentiable lower/upper    bound of the mutual information

[Audio] Our theoretical contributions include optimal graph augmentation and multiplex graph fusion. We define optimal graph augmentation from the perspective of mutual information and demonstrate that guidance from the optimal augmented graph can capture complete task-relevant information, providing a theoretical basis for unsupervised learning. Additionally, we prove that the fused graph contains more task-relevant information compared to the refined graph from a single view, ensuring the effectiveness of multiplex graph fusion.. 

Scene 7

Definition 2. GI is an optimal augmented graph of Gi if and only if I (GI • Gi) I (Y; Gi), implying
that the only information shared between Gi and GI is task-relevant without task-irrelevant noise.
Theorem 1. If GI is the optimal augmented graph of Gz, then I (GSi' G(.) I (G}; Y) holds.
Theorem 2. The maximization of I(G?• GI) yields a discernible reduction in the task-irrelevant
information relative to the maximization of I (G} • Gi).

Theorem 3. The learned fused graph GS contains more task-relevant information than the refined
graph G} from any single view. Formally, we have:
I(GS; Y) Y)
(7)
Theorem 3 theoretically proves that the fused graph GS can incorporate more task-relevant infor-
mation than considering each view individually, thus ensuring the effectiveness of multiplex graph
fusion.

[Audio] We evaluate the learned graph on node clustering and node classification tasks. Our method was tested on four real-world benchmark multiplex graph datasets and compared against several baselines. The results demonstrate that our approach not only outperforms existing unsupervised methods but also competes favorably with supervised approaches, highlighting its effectiveness.. 

Scene 8

Table l: Quantitative results (%) on node clustering. The top 3 highest results are highlighted with
red boldface, red color and boldface, respectively. The symbol "00M" means out of memory.
ACM
DBLP
Method
VGAE
DGl
02MAC
MvAGC
MCGC
HDMI
MGDCR
DMG
BTGF
InfoMGF-RA
InfoMGF-LA
Yelp
NMI
45.83
52.94
42.36
64.49
60.21
65.44
58.8
64.14
68.92
74.89
76.53
AR1
41.36
47.55
46.04
66.81
50.72
68.87
55.15
67.21
73.14
81.09
81.49
ACC
67.93
65.36
77.92
87.17
65.62
88.11
73.82
87.11
90.09
92.82
93.45
Fl
68.62
57.34
78.01
87.21
54.78
88.14
70.34
87.23
90.11
92.89
93.42
NMI
61.79
65.59
58.64
50.39
65.56
64.85
62.47
69.03
66.28
70.19
73.22
AR1
65.56
70.35
60.01
51.21
71.51
70.85
62.22
73.07
72.47
73.49
78.49
ACC
84.48
86.88
83.29
78.39
87.96
87.39
81.91
88.45
88.05
88.72
91.08
83.67
86.02
82.88
77.84
87.47
86.75
80.16
87.88
87.28
88.31
90.69
NMI
39.19
39.42
39.02
24.39
38.35
60.81
44.23
65.66
69.97
72.67
75.18
AR1
42.57
42.62
42.53
29.25
35.17
59.35
46.47
66.33
73.53
74.66
78.91
ACC
65.07
65.29
65.07
63.14
65.61
79.56
72.71
88.26
91.39
91.85
93.26
Fl
56.74
56.79
56.74
56.7
57.49
77.6
54.43
89.27
92.32
92.86
94.01
NMI
53.56
48.15
54.43
48.72
56.65
MAG
AR1 ACC
OOM
42.6 59.89
OOM
00M
OOM
34.92 51.78
43.98 61.37
39.77 61.61
OOM
45.25 64.13
00M
Fl
57.17
49.8
60.53
60.16
63.09
Table 2: Quantitative results with standard deviation (% ± a) on node classification. Available data
for GSL during training is shown in the first column, supervised methods depend on Y for GSL. The
symbol " " indicates that the method is structure-fixed, which does not learn a new structure.
Available
Data for GSI-
x,Y,A
x,Y,A
x,A
x,A
x,A
x,A
x,A
Methods
GCN
GAT
HAN
I-DS
GRCN
IDGI-
ProGNN
GEN
NodeFormer
SUBLIME
STABLE
GSR
HDMI
DMG
BTGF
InfoMGF-RA
InfoMGF-LA
ACM
DBLP
Yelp
Macro-Fl
90.27±0.59
91.52±0.62
91.67±0.39
92.35±0.43
93.04±0.17
91.69±1.24
90.57±1.03
87.91±2.78
91.33±0.77
92.42±0.16
83.54±4.20
92.14±1.08
91.01±0.32
90.42±0.36
91.75±0.11
93.21±0.22
93.42±0.21
Micro-Fl
90.18±0.61
91.46±0.62
91.47±0.22
92.05±0.26
92.94±0.18
91.63* I .24
90.50±1.29
87.88±2.61
90.60±0.95
92.13±0.37
83.38±4.51
92.11±0.99
90.86±0.31
90.31+0.35
91.62±0.11
93.14±0.21
9335±0.21
Macro-Fl
90.01±0.32
90.22±0.37
90.53±0.24
88.11±0.86
88.33±0.47
89.65±0.60
83.13±1.56
89.74±0.69
79.54±0.78
90.98±0.37
75.18±1.95
76.59±0.45
89.91±0.49
90.42+0.57
90.71±0.24
90.99±0.36
91.28±0.31
Micro-Fl
9099±0.28
91.13±0.40
91.47±0.22
88.74±0.85
89.43±0.44
90.61±0.56
84.83±1.36
90.65±0.71
80.56±0.62
91.82±0.27
76.42±1.95
77.69±0.42
90.89±0.51
91.34+0.49
91.57±0.21
91.93±0.29
92.12±0.28
Macro-Fl
78.01±1.89
82.12±1.47
88.49±1.73
75.98±2.35
76.05±1.05
76.98±5.78
51.76±1.46
80.43±3.78
91.69±0.65
79.68±0.79
71.48±4.71
83.85±0.76
80.73±0.64
91.61+0.62
92.81±1.12
93.09±0.27
93.26±0.26
Micro-Fl
81.03±1.81
84.43±1.56
88.78±1.40
78.14±1.98
80.68±0.96
79.15±5.06
58.39±1.25
82.68±2.84
90.59±1.21
82.99±0.82
76.62±2.75
85.73±0.54
84.05±0.91
90.24±0.81
9137±1.28
92.02±0.34
92.24±0.34
MAG
Macro-Fl Micro-Fl
75.98±0.07 75.76±0.10
OOM
00M
00M
OOM
00M
OOM
00M
77.21±0.18 77.08±0.19
75.96±0.05 75.71±0.03
00M
OOM
72.22±0.14 71.84±0.15
76.34+0.09 76.13±0.10
OOM
77.25±0.06 77.11±0.06
OOM

[Audio] We visualized the graph structure and node representations. The Graph Visualization shows the original subgraph structures and the learned graph structure from the ACM dataset. It can be observed that the learned fused graph retains task-relevant information from different views and exhibits a high degree of homophily. The Node Correlation Visualization rearranges nodes by category and calculates the correlation of their representations. It reveals that nodes of the same category have higher representation correlations, demonstrating the effectiveness of our unsupervised method in capturing task-relevant information.. 

Scene 9

Cl
(a) PAP
(b) PSP
Figure 3: Heatmaps of the subgraph adjacency matrices of the original and learned graphs on ACM.

(a) ACM
(b) DBLP
(c) Yelp
Figure 5: Node correlation maps of representations reordered by node labels.

[Audio] In summary, our research revisits two critical aspects of Unsupervised Multiplex Graph Learning: graph structure reliability and multiplex graph non-redundancy. Following a data-centric research paradigm, we learn a fused graph from the original multiplex graph structures in an unsupervised manner, removing irrelevant noise while retaining task-relevant information. Theoretical analysis and extensive experiments demonstrate the effectiveness of our approach. Thanks for your listening.. 

Scene 10

❖ Key takeaways:
 · GSL perspective:    Explore graph structure learning in heterogeneous multiplex graph through a data-centric    paradigm.
 · Beyond redundancy:     Emphasize the importance of unique task-relevant information to better adapt to real-    world non-redundant scenarios.

Our github repository contains the source code and datasets of InfoMGF.

Contact me for discussions!
 E-mail: zhixiang.zxs@gmail.com

空白演示

Hello, everyone. I am Zhi xiang Shen, a senior undergraduate student from the University of Electronic Science and Technology of China. Today, I will be presenting our paper accepted at NeurIPS 2024, titled 'Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning.' This research was conducted by Zhi xiang Shen, Shuo Wang, and Zhao Kang from the University of Electronic Science and Technology of China. You can find the link to our paper and the code via the QR codes shown on the slide.

avatar

Let's start with an introduction to multiplex graphs. A multiplex graph is a special type of multi-relational heterogeneous graph with multiple layers spanning a common set of nodes. These graphs are particularly useful because they provide richer information and better modeling capabilities compared to single-layer graphs. Our focus is on Unsupervised Multiplex Graph Learning, which aims to learn node representations by leveraging diverse graph structures and features without manual labeling. This approach is crucial for applications where labeled data is scarce or unavailable. Unsupervised Multiplex Graph Learning has various applications, including biological network analysis, social network mining, and recommendation systems.

However, there are overlooked aspects in U-M-G-L-. First, the reliability of the graph structure can be compromised by task-irrelevant information such as irrelevant, heterophilic, and missing edges. This noise can significantly degrade the performance of graph learning algorithms. Therefore, beyond graph-fixed methods need to be explored to adapt to real-world noisy data. Second, there is the issue of multiplex graph non-redundancy, where task-relevant information exists not only in shared information between graphs but also within the unique information of certain graphs. In multiplex graph data, shared task-relevant information can manifest as homophilic edges common to all graphs, while unique task-relevant information is reflected in homophilic edges that appear only in a specific graph.  This means that simply focusing on shared information can lead to the loss of valuable insights.

Based on the above observations, we first theoretically define Multiplex Graph Non-redundancy from the perspective of mutual information. Two graph structures are non-redundant with respect to label information if and only if the conditional mutual information is strictly greater than zero. We further conducted empirical analyses on real multiplex graph datasets. The related tables show the unique relevant edge ratio in each graph, which measures the graph-unique task-relevant information. It can be observed that non-redundancy is widespread in real data, highlighting the limitations of existing methods that only capture shared information.

We define our research problem from the perspective of graph structure learning. The goal is to learn a fused graph from the original multiplex graph in an unsupervised manner, mitigating task-irrelevant noise while retaining sufficient task-relevant information. This is achieved by refining the graph structure to remove irrelevant edges and by ensuring that both shared and unique task-relevant information are preserved.

We propose an Information-aware Unsupervised Multiplex Graph Fusion method. Our approach takes the original multiplex structures and node features as input without requiring label information, and outputs the learned structure and node representations. First, we remove irrelevant noise from each graph view. Meanwhile, we maximize both shared and unique task-relevant information for each graph. To capture unique task-relevant information in an unsupervised manner, we propose a learnable generative graph augmentation. Finally, the entire optimization process is performed using a differentiable lower/upper bound of the mutual information, ensuring an accurate estimation of mutual information.

Our theoretical contributions include optimal graph augmentation and multiplex graph fusion. We define optimal graph augmentation from the perspective of mutual information and demonstrate that guidance from the optimal augmented graph can capture complete task-relevant information, providing a theoretical basis for unsupervised learning. Additionally, we prove that the fused graph contains more task-relevant information compared to the refined graph from a single view, ensuring the effectiveness of multiplex graph fusion.

We evaluate the learned graph on node clustering and node classification tasks. Our method was tested on four real-world benchmark multiplex graph datasets and compared against several baselines. The results demonstrate that our approach not only outperforms existing unsupervised methods but also competes favorably with supervised approaches, highlighting its effectiveness.

We visualized the graph structure and node representations. The Graph Visualization shows the original subgraph structures and the learned graph structure from the A-C-M dataset. It can be observed that the learned fused graph retains task-relevant information from different views and exhibits a high degree of homophily. The Node Correlation Visualization rearranges nodes by category and calculates the correlation of their representations. It reveals that nodes of the same category have higher representation correlations, demonstrating the effectiveness of our unsupervised method in capturing task-relevant information.

In summary, our research revisits two critical aspects of Unsupervised Multiplex Graph Learning: graph structure reliability and multiplex graph non-redundancy. Following a data-centric research paradigm, we learn a fused graph from the original multiplex graph structures in an unsupervised manner, removing irrelevant noise while retaining task-relevant information. Theoretical analysis and extensive experiments demonstrate the effectiveness of our approach. Thanks for your listening.