Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning
Authors: Zhixiang Shen
Shuo Wang
zhao kang
Venue: NeurIPS 2024 poster (2024)
Keywords: Multiplex Graph Learning
Graph Structure Learning
Multi-view Graph Clustering
Self-supervised Graph Learning
Primary area: graph_neural_networks

Abstract: Unsupervised Multiplex Graph Learning (UMGL) aims to learn node representations on various edge types without manual labeling. However, existing research overlooks a key factor: the reliability of the graph structure. Real-world data often exhibit a complex nature and contain abundant task-irrelevant noise, severely compromising UMGL's performance. Moreover, existing methods primarily rely on contrastive learning to maximize mutual information across different graphs, limiting them to multiplex graph redundant scenarios and failing to capture view-unique task-relevant information. In this paper, we focus on a more realistic and challenging task: to unsupervisedly learn a fused graph from multiple graphs that preserve sufficient task-relevant information while removing task-irrelevant noise. Specifically, our proposed Information-aware Unsupervised Multiplex Graph Fusion framework (InfoMGF) uses graph structure refinement to eliminate irrelevant noise and simultaneously maximizes view-shared and view-unique task-relevant information, thereby tackling the frontier of non-redundant multiplex graph. Theoretical analyses further guarantee the effectiveness of InfoMGF. Comprehensive experiments against various baselines on different downstream tasks demonstrate its superior performance and robustness. Surprisingly, our unsupervised method even beats the sophisticated supervised approaches. The source code and datasets are available at https://github.com/zxlearningdeep/InfoMGF.

Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning
Zhixiang Shen, Shuo Wang. Zhao Kang
School of Computer Science and Engineering. University of Electronic Science and Technology of China, Chengdu, Sichuan, China zhixiang zxa@gmail. mommail.com com zkanghuestc. edw.eeeett.euu..... cn
Abstract
Unsupervised Multiplex Graph Learning (UMGL) aims to learn node representa- tions various edge types without manual labeling. However, existing research overlooks a key factor: the reliability of the graph structure. Real-world data of- ten exhibit complex nature and contain abundant task-irrelevant noise, severely compromising UMGL's performance. Moreover, existing methods primarily rely contrastive learning maximize mutual information across different graphs, limiting them to multiplex graph redundant scenarios and failing to capture view- unique task-relevant information. In this paper, focus more realistic and challenging task: to unsupervisedly learn fused graph from multiple graphs that preserve sufficient task-relevant information while removing task-irrelevant noise. Specifically, our proposed Information-awer
Unsupervised Multiplex Graph Fusion framework (InfoMGF) uses graph structure refinement to elimi- nate irrelevant noise and simultaneously maximizes view-shared and view-unique task-relevant information, thereby tackling the frontier of non-redundant multiplex graph. Theoretical analyses further guarantee the effectiveness of InfoMGF. Com- prehensive experiments against various baselines on different downstream tasks demonstrate its superior performance and robustness. Surprisingly, our unsuper- vised method even beats the sophisticated supervised approaches. The source code and datasets available at
Introduction
Multiplex graph (multiple graph layers span across common set of nodes), as special type of heterogeneous graph, provides richer information and better modeling capabilities, leading to challenges in learning graph representation [1]. Recently, unsupervised multiplex graph learning (UMGL.) has attracted significant attention due its exploitation of more detailed information from diverse sources [2, 3], using graph neural networks (GNNs) [4] and self-supervised techniques [5]. UMGL has become powerful tool numerous wal-world applications [6, 7], e.g., social network mining and biological network analysis, where multiple relationship types exist various interac- tion types occur.
Despite the significant progress made by UMGL, substantial gap in understanding how to take advantage of the richness of the multiplex view is still left. In particular, fundamental issue is largely overlooked: the reliability of graph structure. Typically, the messaging-pastee in GNNs assumes the reliability of the graph structure, implying that the connected nodes tend to have similar labels. All UMGL methods are graph-fixed fixed, assuming that the original structure is sufficiently reliable for learning [3, 8-10]. Unfortunately, there has been evidence that practical
mechanism
Equaal contribution. Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Shared intormttio (6)
Unraaa sohooum eoper (NJ
Graph
shever sdge
G
Indlowani sdga
Leique inforation 1T 162
information 166
Cruph
(a) Multiplex graph non-redunaancy (b) Non Kon-redundancy example
(c) Empirical study on ACM
(a) and (b) illustrate that a non-redundant multiplex graph, view-specific task-relevant edges exist in certain graphs. The color of nodes represents class, edges between nodes of the same class are considered relevant edges, and "unique" indicates that the edge exists only one graph. (c) The unique relevant edge ratio (the number of unique relevant edges) (the total number of relevant edges in this graph). Each graph contains a significant amount of unique task-relevant information.
Figure I:
graph structures are not always reliable [11]. Multiplex graphs often contain substantial amounts of less informative edges characterized by irrelevant, misleading, and missing connections. For example, due to the heterophily in the graphs, GNNs generate poor performance [12-14]. Another representative example is adversarial attacks [15], where attackers tend to add edges between nodes of different classes. Then, aggregating information from neighbors of different classes degrades UMGL performance. Diverging from existing approaches to node representation learning, we focus on structure learning of a new graph from multiplex graphs to better suit downstream tasks. Notably, existing Graph Structure Learning (GSL) overwhelmingly concentrated on a single homogencous graph [16], marking our endeavor as pioneering in the realm of multiplex graphs.
Given the unsupervised nature, the majority of UMGL methods leverage contrastive learning mecha- nism [8-10], a typical self-supervised technique, for effective training. However, recent research has demonstrated that standard contrastive learning, maximizing mutual information between different views, limited to capturing view-shared task-relevant information [17]. This approach is effective only in multi-view redundant scenarios, thereby overlooking unique task-relevant information spe- cific to each view. In practice, the multiplex graph is inherently non-redundant. As illustrated in Figure I, task-relevant information resides not only in shared areas across different graph views but also in specific view-unique regions. For instance, in the real citation network ACM [18], certain papers on the same subject authored by different researchers may share categories and thematic rel- evance. This characteristic, compared to the co-author view, represents view-unique task-relevant information within the co-subject view. It exposes critical limitation existing UMGL methods, which potentially cannot capture sufficient task-relevant information.
Motivated by the above observations, research goal be summarized follows: how learn a fused graph from the original multiplex graph in an unsupervised manner, mitigating task- irrelevant noise while retaining sufficient task-relevant information? ? To handle this new task. we propose novel information-awatt Unsupervised Multiplex Graph Fusion framework (InfoMGF). Graph structure refinement first applied each view achieve more suitable graph with less task-irrelevant noise. Confronting multiplex graph non-redundancy. InfoMGF simultaneously maxi- mizes the vieweshared and tiequunique task-relevant information to realize sufficient graph learning. A learnable graph augmentation generator is also developed. Finally, InfoMGF maximizes the mu- tual information between the fused graph and each refined graph to encapsulate clean and holistic task-relevant information from range of various interaction types. Theoretical analyses guarantee the effectiveness of our approach in capturing task-relevant information and graph fusion. The un- supervised learned graph and node representations can be applied to various downstream tasks. In summary, our main contributions are three-fold:
Problem. We pioneer the investigation of the multiplex graph reliability problem in principled way, which a more practical and challenging task. our best knowledge, we are the first to attempt unsupervised graph structure learning in multiplex graphs

---

Multiplex Graph
Graph Structure Refinement
Task-relevant Information Maximizing
Graph.Sug
Optinal
Paramsters
Updata
Refined Graph
Maximize Mutual
Information
G
Graph Learner
Fased Graph
Graph Encuder
Shared
Nadle Clastwring
Tasks
Refined Graph
Unigue Tade-
Gp
Shared Information
AraphAug
Optimal
Gj
1100
Graph Fusion
The overall framework of the proposed InfoMGF. Specifically, InfoMGF first generates refined graphs and the fused graph through the graph learner. Subsequently, it maximizes shared and unique task-relevant information within the multiplex graph and facilitates graph fusion. The learned fused graph and node representations used for various downstream tasks.
Figure 2:
Algorithm. We propose InfoMGF, a versatile multiplex graph fusion framework that steers the fused graph learning by concurrently maximizing both view-shared and view-unique task-relevant information under the multiple graphs non-redundancy principle. Further- more, we develop two random and generative graph augmentation strategies capture view-unique task information. Theoretical analyses ensure the effectiveness of InfoMGF.
Evaluation. We perform extensive experiments against various types of state-of-the-ar methods different downstream tasks to comprehensively evaluate the effectiveness and robustness of InfoMGF. Particularly, our developed unsupervised approach even outper- forms supervised methods.
2 Preliminaries
Notation. The multiplex graph is represented by G (GI,..,Gy') where Go (Au, X} the w-th graph. A, E 10,1).xx is the corresponding adjacency matrix and X E Nxdy is the shared feature matrix across all graphs. X; Rd is the i-th of X, representing the feature vector of node N is the number of nodes and D. is diagonal matrix denoting the degree matrix of A.. Y label information. For convenience, use "view" to refer to each graph in the multiplex graph.
Multiplex graph non-redundancy. Task-relevant information exists not only in the shared infor- mation between graphs but also potentially within the unique information of certain graphs. Fol- lowing the non-redundancy principle [17], we provide the formal definition of Multiplex Graph Non-redundancy:
Definition 1. G; is considered non-redundant with Gj for Y if and only if there exists > 0 such IG;;; Y G() >6
that the conditional mutual information I[G;; Y G₃) )
Graph structure learning, Existing GSL methods primarily focus on single graph. Their pipeline can be summarized a two-stage framework [16]: a Graph Learner takes the original graph G = {AA, X to generate refined graph G = {A*, with a new structure; Graph Encoder uses the refined graph as input to obtain node representations. Note that node features generally do not change in GSL, only the graph structure is optimized. Related work is in Appendix B.
3 Methodology
As illustrated in Figure 2, our proposed InfoMGF consists of two modules: the Graph Structure Refinement module and the Resk-Relevant Information Maximization module.

---

3.1 Graph Structure Refinement
We first use graph learner generate each view's refined graph G; (A,, To retain node features and structure information simultaneously, we apply the widely used Simple Graph Con- volution (SGC) [19] to perform aggregation in each view, resulting view-specific node features X A view-specific two-layer attentive network is employed to model the varying contributions of different features to structure learning:
(I) where D. = De and Ag Ar + I. represents the order of graph aggregation. a(.) is the non-linear activation function and denotes the Hadamard product. All rows of WT are identical, representing a learnable attention vector shared by all nodes. This strategy enables us to acquire view-specific features before training, thereby circumventing the time-consuming graph convolu- tion operations typically required by GNN-based graph learners during training, which significantly boosts our model's ' scalability.
= A =²=o(X" & (T) + W
Like existing GSL methods [16, 20], we apply post-processing techniques to ensure that the adja- cency matrix A satisfies properties such as sparsity, non-negativity, symmetry, and normalization. Specifically, we use H" to construct the similarity matrix and then sparsify it using k-nearest neigh- bors (I:NN). For large-scale graphs, we utilize aecality-sensitii approximation during kNN sparsifi- cation to reduce time complexity [21]. Afterward, operations including Symmetrization, Activation, and Normalization are used sequentially
generate the final A Following the refinement of each view, we employ shared Graph Convolutional Network (GCN) [22] as the graph encoder to obtain the node representations Z" R Nxd xd of each view, computed by Z GCN(A X).
3.2 Maximizing Shared Eask-Relevant Information
G should contain not only view-shared but also view-unique task-relevan information. Following standard contrastive learning [23, 24], for each pair of distinct views (e.g.. and j). our approach seeks to maximize the mutual information 0.5I Gy) + 0.5I(G); G,) to capture shared task- relevant information between views.
Proposition 1. For any view i and j, 2I;;; Gj) is the lower bound of I( G2) + I(G]: G.).
Detailed proofs are provided in the Appendix D. According to Proposition 1, the maximization objective can be transformed to a tractable lower bound [(;;; Gj). Considering the addition of mutual information for each pair, the loss term for minimization can be expressed follows:
v
2
C, = V(V - 1) j=
I G3)
(2)
3.3 Maximizing Unique Task-Relevant Information
Maximizing view-unique task-relevant information can be rigorously expressed as maximizing I[;;; Y| Ujzs Gy). Then, we relax the optimization objective to the total task-relevant informa- tion within the view, I(G;; Y). This decision is based on the following considerations: hand, deliberately excluding shared rask-relevant information unnecessary and would complicate the optimization process. On the other hand, repeated emphasis on shared task-relevant information encourages the model to focus more on it in the carly training stage.
the one
The unsupervised nature of our task dictates that we cannot directly optimize [[;;; Y) using label information. Some typical graph learning methods often reconstruct the graph structure to pre- serve the maximum amount of information from the original data [25-27]. In the context of our task, this reconstruction-bant based optimization objective is equivalent maximizing the mutual infor- mation with the original graph structure [28, 29], i.e., I[G;; G.). However, such methods have significant drawbacks: they retain iask-inrelevant information from the original data, and the graph reconstruction also entails high complexity. In contrast, we leverage graph augmentation to reduce task-irrelevant information and retain task relk-ntl information without accessing Y. Following the optimal augmentation assumption [17, 30], we define optimal graph augmentation as:

---

Definition 2. G. is an optimal augmented graph Gf G. ifa only if I'';; G.) IYY; implying that the only information shared between G, and G2 resk-relevant without task-irrelevant noise.
Theorem 1. If G. is the optimal augmented graph of G. then [(C,; I Y) holds.
Theorem 2. The maximization of I[G;; G²) yields a discernible reduction in the task-irrelevant information relative to the maximization of (G;; Gt).
Theorem I theoretically guarantees that maximizing [[;;; would provide clean and sufficient task-relevant guidance for learning G. Theorem 2 demonstrates the superiority of our optimization objective over typical methods in removing task-irrelevant information. Therefore, given G² {A,, for each view, where A and X' denote the augmented adjacency matrix and node features, respectively, the loss term L, is defined as:
Lu = V Σ G(
1
The key to the above objective lies in ensuring that G. satisfies the optimal graph augmentation. However, given the absence of label information, achieving truly optimal augmentation is not feasi- ble; instead, we can only rely on heuristic techniques to simulate it. Consistent with most existing graph augmentations, we believe that task-relevant information in graph data exists in both struc- ture and feature, necessitating augmentation in both aspects. We use random masking, simple yet effective method, to perform feature augmentation. For graph structure, we propose two versions: random edge dropping and learnable augmentation through graph generator.
Random feature masking. For node features, we randomly select a fraction of feature dimensions and mask them with zeros. Formally, we sample random vector m E {0, 10,1) where each di- mension drawn from a Bernoulli distribution independently, i.e., my ~ Bern(1 - p). Then, the augmented node features X' is computed by X' [X1 @ X2 O m; ...; Xx m] m]..
Random edge dropping (InfoMGF-RA). For a given A,, masking matrix M E {0, 10,1NNxN, is randomly generated, where each element Mi is sampled from Bernoulli distribution. Afterward, the augmented adjacency matrix can be computed as A,, = A. @ M.
Learnable generative augmentation (InfoMGF-LLA), Random edge dropping may lack reliability and interpretability. A low dropping probability might not suffice to eliminate task-irrelevant infor- mation, while excessive deletions could compromise task-relevant information. Therefore, we opt to use a learnable graph augmentation generator. To avoid interference from inappropriate struc- ture information, by employing a Multilayer Perceptron (MLP) in the node features. To ensure the differentiability of the sampling operation for end-to-end training, we introduce the Gumbel-Max reparametrizzaioon trick [31, 32] to transform the discrete binary (0-1) distribution edge weights into a continuous distribution. Specifically, for each edge Cs, in view v, its edge weight wV, in the corresponding augmented view is computed as follows:
compute personalized sampling probabilities for existing edges in each view
8h MLP ([ WX,),, wH, = Sigmoid (llog 8 log(1 8) + 07,)
where [ denotes the concatenation operation and 5 Uniform((, 1) the sampled Gumbel random variate. We can control the temperature hyper-parameter approaching 0 to make wH, tend towards binary distribution. For an effective augmented graph generator, it should eliminate task-irrelevant noise while retaining task-relevant information. Therefore, design a suitable loss function for augmented graph training:
N ΣΣ 1=1 j=1
V
TX) |X3||| ||*3|||
V Σ GG 1=1
Cgen
+ A
(5)
NV
where À is a positive hyper-parametts parameter. The first term reconstructs view-specific features using the cosine error, guaranteeing that the augmented views preserve crucial relk-aelevant information while having lower complexity compared to reconstructing the entire graph structure. The reconstructed features X are obtained using an ML.-based Decoder the node representations 2' of the aug- mented view. The second term minimizes T G.) to regularize the augmented views simultane- ously, ensuring that the augmented graphs would provide only task-relevan information as guidance
5

---

with less task-irred irrelevant noise when optimizing the refined graph G through (3,(3). Note that for InfoMGF-LA, we adopt an iterative optimization strategy update G and G2 alternatively, as described in Section 3.4.
Although previous work also employs similar generative graph augmentation [33], still possess ir- replaceable advantages in comparison. Firstl, they merely minimize mutual information to generate the augmented graph, lacking the crucial information retention component, which may jeopardize lask-relevant information. Furthermore, an upper bound should ideally be used for minimization, whereas they utilize lower bound estimator for computation, which is incorrect in optimization practice. In contrast, we use a rigorous upper bound of mutual information for the second term of Lyen. which is demonstrated later.
3.4 Multiplex Graph Fusion
The refined graph retains task-relevant information from each view while eliminating inteeante noise. Afterward, we learn a fused graph that encapsulates sufficient task-relevant information from all views. Consistent with the approach in Section 3.1, we leverage scalable attention mechanism as the fused graph learner:
H = ===o(xxx : x''oo''ow,, f
1 E IGG
(6)
where the node features concatenated with all view-specific features input. The same post- processing techniques are sequentially applied to generate the fused graph G = {A*, X). The node representations Z of the fused graph are also obtained through the same GCN. We maximize the mutual information between the fused graph and each refined graph to incorporate task-relevant information from all views, denoted loss Ly. The total loss L of our model can be expressed as the sum of three terms: L = L. + Lu + L..
The learned fused graph G* contains more task-relevant information than the refined graph G from any single view. Formally, we have;
Theorem 3.
I(G Y) 2 max (GG; Y)
Theorem 3 theoretically proves that the fused graph G can incorporate more task-relevant infor- mation than considering each view individually, thus ensuring the effectiveness of multiplex graph fusion.
Optimization, Note that all the loss terms require calculating mutual information. However, di- rectly computing mutual information between two graphs is impractical due to the complexity of graph-structured data. Since we focus on node-level tasks, we assume the optimized graph should guarantee that each node's neighborhood substructure contains sufficient task-relevant information. Therefore, this requirement can be transferred into mutual information between node representations [34], which can be easily computed using a sample-bass based differentiable lower/upper bound. For any view i and j. the lower bound In and upper bound lub of the mutual information I (ZZ; Z²) are [17]:
log expf(2t, 21+)
Iwo Z2) E aptetitt )m(()))
(8)
EN expf(2* (=tp 25)
Tub (3): E B2t (5* 20+]]]]]]]]]]]]]]]]
E Bx(p((=)) [ zlmp(==')
where f(..) .) is a score critic approximated by a neural network and f* is the optimal critic from In plugged into the Lub objective. p(2', denotes the joint distribution of node representations from views and j. while p(=") denotes the marginal distribution. z and 27+ are mutually positive samples, representing the representations of the same node in views i and respectively.
To avoid too many extra parameters, the function ,(=1, is implemented using non-linear projec- tion and cosine similarity. Each term in the total loss L maximizes mutual information, so we use the lower bound estimator for the calculation. contrast, we use the upper bound estimator for the generator loss Eyen in InfoMGF-LA, which minimizes mutual information. These two losses can

---

be expressed as follows:
V
1 V
L = V(V
2
Ib 22)
Tzo 2n)
(Z; )*)
(10)
V
V 1=1
1=1 ,=
1=1
ggen
1 NV
11-
(x |X3|| -129|1
A
1 V
Tus( %²)
(11)
Finally, we provide the InfoMGF-LA algorithm in Appendix C.I. In Step I of each epoch, we keep the augmented graph fixed and optimize both the refined graphs and the fused graph using the total loss L. updating the parameters of Graph Learners and GCN. In Step 2, we keep the refined graphs fixed and optimize each augmented graph using Lgens updating the parameters of the Augmented Graph Generator and Decoder. After training, G and Z are used for downstream tasks.
4 Experiments
In this section, our aim is to answer three research questions: RQ1: How effective is InfoMGF for different downstream tasks in unsupervised settings? RQ2: Does InfoMGF outperform baselines of various types under different adversarial attacks? RQ3: How do the main modules influence the performance of InfoMGF?
4.1 Experimental Setups
Downstream tasks. We evaluate the learned graph on node clustering and node classification tasks. For node clustering, following [8], apply the K-means algorithm the node representations Z of G and use the following four metrics: Accuracy (ACC), Normalized Mutual Information (NMI), Fl Score (F1), and Adjusted Rand Index (ARI). For node classification, following the graph structure learning settings in [16], we train a new GCN on G for evaluation and use the following two metries: Macro-F1 and Micro-F1.
Datasets. We conduct experiments on four real- world benchmark multiplex graph datasets, which consist of two citation networks (i.e., ACM [18] and DBLP [18]), review network Yelp [35] and a large-scale citation network MAG [36]. Details of datasets are shown in Appendix E.
Baselines. For node clustering, we compare InfoMGF with two single-graph methods (i.e., VGAE [25] and DGI [37]) and seven multiplex graph methods (i.e., O2MAC [26], MvAGC [38], MCGC [39], HDMI [8], MGDCR [9], DMG [3], and BTGF [10]). All the baselines are unsupervised clustering methods. For a fair comparison, we conduct single-graph methods separately for each graph and present the best results.
For node classification, we compare InfoMGF with basclines of various types: three supervised structure-fixed GNNs (i.c., GCN [22]. GAT [40] and HAN [41]), six supervised GSL methods (i.c.,
LDS [42], GRCN [43], IDGL [44], ProGNN [11], GEN [45] and NodeFormer [46]), three unsuper- vised GSL methods (i.e., SUBLIME [20]. STABLE [47] and GSR [48]), and three structure-fixe fixed UMGL methods (i.e., HDMI [8], DMG [3] and BTGF [10]). GCN, GAT, and all GSL methods are single-ge gaggl-graphhaae approaches. For unsupervised GSL methods, following [20], we train a new GCN on the learned graph for node classification. For UMGL methods, following [8], we train a linear classifier on the learned representations. Implementation details can be found in Appendix E.2.
4.2 Effectiveness Analysis (RQ1)
Table presents the results of node clustering. Firstly, multiplex graph clustering methods outper- form single graph methods overall, demonstrating the advantages of leveraging information from multiple sources. Secondly, compared to other multiplex graph methods, both versions of our ap- proach surpass existing state-of-the-art methods. This underscores the efficacy of our proposed graph structure learning, which eliminates task-irrelevant noise and extracts tesk-relevant informa- tion from all graphs, to serve downstream tasks better. Finally, InfoMGF-LA achieves notably su- perior results, owing to the exceptional capability of the learnable generative graph augmentation in capturing view-unique task-relevant information.
7

---

Table 1: Quantitative results (%) on node clustering. The top 3 highest results highlighted with red boldface, red color and boldface, respectively. The symbol "OOM" means out of memory.
Method
ACM
DBLP
Yelp
MAG
NMI
ARI
ACC
Fl
NMI
ARI
ACC
F1
NMI
ARI
ACC
F1
NMI
ARI
ACC
Fl
VGAE
15.83
11.36
67.93
62
61.79
65.56
84.48
83.67
39.19
42.57
65.07
56.74
OOM
DGI
57.34
65.59
70.35
56.02
39:42
65.29
57.17
O2MAC
42.36
46.04
77.92
78.01
58.64
60.01
83.29
82.85 88
39.02
42.53
65.07
56.74
OOM
MVAGC
64.49
66.81
87.17
87.21
501.9
51.21
73 39
TT.48 :4
24.39
29.25
63,14
56.7
ODM
MOGC
60.21
50.72
65.62
54.78
65.56
87.96
87.47
38.35
65.61
$7.49
ODM
HDMI
64.85
70.85
87.39
S6.75
49.8
MGDCR
58.8
55.15
75.82
34
62.47
62.22
81 91
80. 16
44.23
46.47
72.71
54.43
$4.43
43.98
37
60.53
DMG
64.14
67.21
87.11
87.23
69.03
73.07
38.45
87.88
65.
66.33
88.26
89.27
48.72
39,77
61.11
60.16
BTGF
68.92
73.14
90.09
66.28
72.47
05
87.28
69.97
73.53
91.39
92.32
ODM
InfoMGF-RA
74,89
81.09
92.82
92.88
70.19
73. 49
72
85. 31
72.67
74.65
91.85
92.86
56.65
45.25
64.13
63,09
InfoMGILLA
76.53
81.49
93.45
93.42
73.22
78.49
91.08
94066
75.18
78.91
93.26
94.01
ODM
Table 2: Quantitative results with standard deviation (% σ) 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 GSL
Methods
ACM
DBLP
Yelp
MAG
Macro-Fi
Micro-F]
Macro-FI
Micro-F1
Macro-FI
Micro-Fi
Macro-F1
MicroFFI
GCN
90.27:10.59
90.18:10.61
90.01=0.322
90.99 28
78.011
81.03:1..11
75.98.10.07
75.76:0.10
GAT
91.52+0022
91.46-+0.62
90.22-0.37
91.13+0.40
82. 12+
84.43+1.56
00M
HAN
91.7740.99
91.47:00222
90.53-0.24
91:47:0.22
88.49+
88.78++1.0 .0
OOM
X.Y.A
LDS
92.3520.43
92.05:10.26
88.11:0.86
08.74:0.85
75. 25.3
78.1421.98
0OM
XYA
GRCN
93,0410.17
88.31-0.47
89.43:10.44
76.051:105
80.68.10.96
OOM
XYA
IDGL
91.6911.24
91.63:11.24
89.65_0.60
90.61
76.98.15.78
79.15:1..06
OOM
X.YAA
ProGNN
90.57+1003
90.50:t1..29
83.13= 1.56
84.83 1.36
$1.76:2:1440
58.29
OOM
X.Y.A
GEN
87.91122778
87.88.12.61
89.74
90.651..771
80.43:13.78
62.68.12.84
OOM
X.YAA
NodeFommrr
91.33+0.77
90.60++0.95
79.54-0.78
80.56+0..2
91.69+0.65
90.59++1221
77.21+00188
77.08+0.19
X.A
SUBLIME
92-42.10.16
92.13:10.37
90.98-0.37
91.82:00.27
79 79.68:10.799
82.99110.82
75.96:20.05
75.7110.03
X.A
STABLE
83 541-4.2
83.38:14.51
75, 18:18:9:
76.42:t:100 .95
71.48:24.71
76.62-42.75
ODM
X.A
12.14.1
92.11:10.99
76.59.0..45
77.6910.44
83.85.10.76
85.73.10.44
OOM
HDMI
910110.32
90.86:10.31
89.91
90.89:10.51
50.73.10.64
84.05.10.91
72.22.10.14
71.8110115
DMG
90.42+0.36
90.31++0.35
90.42:0.577
91 04:4944499
91.61+0622
90.24++0.1
76.34-0.09
76.13+0.10
91.7540.11
91.62:10.11
91:57:20221
92.81:1.112
91.37::1.28
OUM
X.A
InfOMGFRR
23:21:20:22
93.14:10.21
90.99:00336 36
09:
93.09:::0227
92.02:10.05 34
77.25:00.66
77.11:0.06
X.A
MMGMMG-LL
93.42.10.21
93.35.10.21
91.28:00.31
92.12:10.28
93.26.10.26
92.24.10.34
OOM
Table 2 reports the node classification results. Overall, GSL methods outperform structure-fixed methods, demonstrating the unreliability of the original structure in real-world data and the signif- icance of graph structure learning. Particularly for various carefully designed UMGL methods, the original graphs with rich task-irrelevant noise severely limit their performance. Compared to exist- ing single-grapi -raph GSL methods, both versions of InfoMGF outperform the supervised methods. By capturing shared and unique information from multiplex graphs, InfoMGF can integrate more com- prehensive task rel-reeevant information. Finally, we can observe that the proposed InfoMGF-LA with learnable augmentation indeed surpasses the random augmentation version, once again highlighting its advantage in exploring task-relevant information.
We select a subgraph from the ACM dataset with nodes in two classes (database (C1) and data min- ing (C2)) and visualize the edge weights in the original multiplex graphs and the fused graph learned by InfoMGF-LA. From Figure 3, the learned graph mainly consists intra-class edges. Compared
0
0
C1
C2
(a) PAP
(b) PSP
(c)
G"
Figure 3: Heatmaps of the subgraph adjacency matrices of the original and learned graphs on ACM.
8

---

Magre Macro-F11S
Macro (1100)
Macro-
75
ScRUPS
85
70
0.0
0.4
0.6
0.5
0.0
0.2
Du4
64
dexttoo
(a) Adding edges
(b) Deleting edges
(c) Masking features
Figure 4: Robustness analysis ACM.
to the nearly fully connected PSP view, InfoMGF significantly reduces inter-class edges, reflecting effective removal of task-irrelevant noise. Compared to the PAP view, InfoMGF introduces more intra-class edges, benefiting from capturing shared and unique task-relevant information from all graphs. Furthermore, varying edge weights in G represent different importance levels, better serving downstream tasks. In summary, the above experiment results across various downstream tasks demonstrate the effectiveness of InfoMGF. We use the InfoMGF-LA version in the subsequent sections to conduct more comprehensive analyses.
Robustness Analysis (RQ2)
To evaluate the robustness of InfoMGF against random noise, we perturb each graph the ACM dataset by randomly adding edges, deleting edges, and masking features. We compare InfoMGF against various baselines: Structure-fixed method (GCN), GSL method (SUBLIME), and UMGL method (HDMI). From Figure 4a and 4b, evident that with increasing rates edge perturbing. the performance of each method deteriorates, while the GSL methods (i.e., InfoMGF and SUB- LIME) exhibit better robustness. Notably, InfoMGF consistently outperforms all other methods across both experimental settings, especially when the perturbation rate is extremely high.
Figure 4c shows the performance InfoMGF and various baselines when injecting random feature noise. It can be observed that InfoMGF exhibits excellent robustness against feature noise, while the performance of SUBLIME degrades rapidly. LIME's performance heavily relies the quality of node features. In contrast, our method can directly optimize task-relevant information multi-view graph structures (e.g., edges shared across multiple graphs are likely to share task-relevant information, which can be directly learned through Cz), thus reducing dependence on node features. Consequently, InfoMGF demonstrates superior robustness against various types of noise.
single graph structure learning method, SUB-
4.4 Ablation Study (RQ3)
Table 3: Performance (% + a) of InfoMGF and its variants.
ACM
DBLP
Yelp
Macro-FI
Micro-FI
Macro-FI
Micro-FI
Macro-F1
Micro-FI
93.05-00.49
92.98-0..99
90.44+0.45
91.39-0.41
98.154-0.12
wlo C.
92.66=0.53
92.61=0.51
90.13:0043
91.05 91.05=0.44
92.23=0.27
90.9220.36
wio Aug.
92.84=0.17
92.81:0.16
90.94:0:45
9181=0011
92,76::0.99
91 91.63-0.51
92.9120.53
92.8820.51
91.0520.27
9187=0.23
92.65:0.27
91.4520.37
InfoMGF
93.42=0.21
93.35=0.21
91.28:0.31
92.12=0.28
93.26#0.26
92.24=0.34
To verify the effectiveness of each part of InfoMGF, we design four variants and compare the classi- fication performance against InfoMGF.
Effectiveness of loss components. Recall InfoMGF maximizes view-shared and unique task-relevant information by L. and C., Thus, we design two variants (w/o L. and w/o C.)) Table 3 shows the necessity of each component. Furthermore, we can observe that the removal of L., has greater im- pact compared to L., which can explained by the fact that optimization of L., actually maximizes the overall task-relevant information of each view, rather than the unique aspects of the view.

---

(a) ACM
(b) DBLP
(c) Yelp
Figure 5: Node correlation maps of representations reordered by node labels.
Effectiveness of augmentation module. The InfoMGF-LA framework incorporates learnable gen- erative augmentation and maximizes the mutual information I [ G)) to mine the task-relevant information. We first compare InfoMGF with maximizing the mutual information I(G]; G₂) with the original graph structure without augmentation (w/o Aug.). Furthermore, we remove the recon- struction loss term (w/o Rec.) of Lgen to analyze the necessity of preserving crucial information. The results show that maximizing [G;; G;) leads to poorer performance compared to [[G;; G.). consistent with Theorem 2. Meanwhile, deleting the reconstruction term from Lgen also results in the augmented graph lacking task-relevant information, thus hurting model performance.
4.5 Node Correlation Visualization
We further visualize the node correlation in the learned representations Z of the fused graph, which used the clustering task. Figure shows the node correlation heatmaps the representations, where both rows and columns are reordered by the node labels. In the heatmap, warmer colors signify a higher correlation between nodes. same class is significantly higher than that of nodes from different classes. This is due to G mainly containing intra-class edges without irrelevant inter-class edges, which validates the effectiveness of InfoMGF in unsupervised graph structure learning.
evident that the correlation among nodes of the
Conclusion and Limitation
This paper delves into the unsupervised graph structure learning within multiplex graphs for the first time. The proposed InfoMGF refines the graph structure eliminate task-irrelevant noise, while simultaneously maximizing both the shared and unique task-relevant information across different graphs. The fused graph applied to downstream tasks is optimized incorporate clean and compre- hensive task-relevant information from all graphs. Theoretical analyses and extensive experiments ensure the effectiveness of InfoMGF. A limitation of our research lies in its focus solely on the pure unsupervised scenario. In some real-world scenarios where partial node labels are available, label information can be used to learn better structure of multiplex graphs. Such supervised or semi-supervised problems are left for future exploration.
Acknowledgments and Disclosure of Funding
This work was supported by the National Natural Science Foundation of China (No. 62276053).
References
[1] Zhixiang Shen, Haolan He, and Zhao Kang. Balanced multi-relational graph clustering. In ACM Multimedia 2024.
10

---

[2] Chanyoung Park. Donghyun Kim, Jiawei Han, and Hwanjo Yu. Unsupervised attributed mul- tiplex network embedding. In Proceedings of the AAAI conference on artificial intelligence. volume 34, pages 5371-5378, 2020.
[3] Yujie Mo, Yajie Lei, Jialie Shen, Xiaoshuang Shi, Heng Tao Shen, and Xiaofeng Zhu. Dis- entangled multiplex graph representation learning. In International Conference on Machine Learning, pages 14983-25006 PMLR, 2023.
[4] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32(1):4-24, 2020.
[5] Xiao Liu, Fanjin Zhang, Zhenyu Hou, Li Mian, Zhaoyu Wang, Jing Zhang, and Jie Tang. Self- supervised learning: Generative contrastive. IEEE Transactions on Knowledge and Data Engineering, 35(1):857-876, 2021.
[6] Weifeng Zhang, Jingwen Mao, Yi Cao, and Congfu Xu. Multiplex graph neural networks for multi-behavior recommendation. In Proceedings of the 29th ACM international conference on information & knowledge management, pages 2313-23 316,, 2020.
[7] Xunqiang Jiang, Tianrui Jia, Yuan Fang, Chuan Shi, Zhe Lin, and Hui Wang. Pre-training on large-scale heterogeneous graph. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 756-766, 2021.
[8] Baoyu Jing, Chanyoung Park, and Hanghang Tong. Hdmi: High-order deep multiplex infomax. In Proceedings of the Web Conference 2021, pages 2414-2424, 2021.
[9] Yujie Mo, Yuhuan Chen, Yajie Lei, Liang Peng, Xiaoshuang Shi, Changan Yuan, and Xiaofeng Zhu. Multiplex graph representation learning via dual correlation reduction. IEEE Transac- tions on Knowledge and Data Engineering, 2023.
[10] Xiaowei Qian, Bingheng Li, and Zhao Kang. Upper bounding barlow twins: A novel filter for multi-relational clustering. In Proceedings the AAAI Conference Artificial Intelligence, volume 38, pages 14660-14668, 2024.
[11] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang. Suhang Wang, and Jiliang Tang, Graph struc- ture learning for robust graph neural networks. Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 66 2020.
[12] Erlin Pan and Zhao Kang. Beyond homophily: Reconstructing structure for graph-agnostic clustering. In International Conference on Machine Learning, pages 2023.
PMLR,
[13] Jiong Zhu, Junchen Jin, Donald Loveland, Michael T Schaub, and Danai Koutra. How does het- erophily impact the robustness of graph neural networks? theoretical connections and practical implications. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2637-2647, 2022.
[14] Bingheng Li, Erlin Pan, and Zhao Kang- Pe-conv: Unifying homophily and heterophily with two-fold filtering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 13437-13445. 2024.
[15] Daniel Zügner,, Oliver Borchert, Amir Akharnejad, and Stephan Günnemann. Adversarial attacks on graph neural networks: Perturbations and their patterns. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1-31, 2020.
[16] Zhixun Li, Xin Sun, Yifan Luo, Yanqiao Zhu, Dingshuo Chen, Yingtao Luo, Xiangxin Zhou, Qiang Liu, Shu Wu, Liang Wang, et al. Gslb: The graph structure learning benchmark. Ad- vances in Neural Information Processing Systems, 36, 2023.
[17] Paul Pu Liang, Zihao Deng, Martin Q Ma, James Y Zou, Louis-Philipee Morency, and Ruslan Salakhutdinov. Factorized contrastive learning: Going beyond multi-view redundancy. Ad- vances in Neural Information Processing Systems, 36, 2023.

---

[18] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
[19] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference machine learning, pages 6861-6871 PMLR, 2019.
[20] Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference 2022, pages 1403, 2022.
[21] Bahare Fatemi, Layla EI Asri, and Seyed Mehran Kazemi. Slaps: Self-supervision improves structure learning for graph neural networks. Advances in Neural Information Processing Systems, 34:22667-22666
2021.
[22] Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016.
[23] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. In Algorithmic Learning Theory, pages 1179-1206. PMLR, 2021.
[24] Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. Self- supervised learning from multi-view perspective. In International Conference on Learning Representations, 2020.
[25] Thomas N Kipf and Max Welling. Variational graph auto-encoders. In Bayesian Deep Learn- ing Workshop (NIPS), 2016.
[26] Shaohua Fan, Xiao Wang, Chuan Shi, Emiao Lu, Ken Lin, and Bai Wang. One2multi graph autoencoder for multi-view graph clustering. In proceedings of the web conference 2020, pages 5070-3076, 2020.
[27] Yawen Ling, Jianpeng Chen, Yazhou Ren, Xiaorong Pu, Jie Xu, Xiaofeng Zhu, and Lifang He. Dual label- label-guided graph refinement for multi-view graph clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 8791-8798. 2023.
[28] Haoqing Wang, Xun Guo. Zhi-Hong Deng, and Yan Lu. Rethinking minimal sufficient repre- sentation in contrastive learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 16041-16050, 2022.
[29] Jintang Li, Ruofan Wu, Wangbin Sun, Liang Chen, Sheng Tian, Liang Zhu, Changhua Meng, Zibin Zheng, and Weiqiang Wang. What's 's behind the mask: Understanding masked graph modeling for graph autoencoders. Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1268-1279, 2023.
[30] Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning? Advances in neural information process- ing systems, 33:6827-688 -8339, 2020.
[31] Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. In International Conference on Learning Representa- lions, 2016
[32] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparametrization with gumble-softmax. In International Conference on Learning Representations (ICLR 2017), 2017.
[33] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances in Neural Information Processing Systems, 11159200-1933, 2021.
[34] Yixin Liu, Kaize Ding, Qinghua Lu, Fuyi Li, Leo Yu Zhang, and Shirui Pan. Towards self- interpretable graph-level anomaly detection. Advances Neural Information Processing Sys- tems, 36, 2024.
12

---

[35] Yuanfu Lu, Chuan Shi, Linmei Hu, and Zhiyuan Liu. Relation structure- aware heterogeneous information network embedding. In Proceedings of the AAAI conference on artificial intelli- gence, volume 33, pages
2019.
[36] Kuansan Wang. Zhihong Shen, Chiyuan Huang. Chieh-Har Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396-413, 2020.
[37] Petar Veličković, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R De- von Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2018.
[38] Zhiping Lin, Zhao Kang, Lizong Zhang, and Ling Tian. Multi-view attributed graph clustering. IEEE Transactions on Knowledge & Data Engineering, 35(02):1872-188) 2023.
[39] Erlin Pan and Zhao Kang. Multi-view contrastive graph clustering. Advances in neural infor- mation processing systems, 34:2148-2159) 2021.
[40] Meng Qu, Jian Tang, Jingho Shang, Xiang Ren, Ming Zhang, and Jiawei Han. An attention- based collaboration framework for multi-view network representation learning. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 1767- 1776, 2017.
[41] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang. Yanfang Ye, Peng Cui, and Philip S Yu. Het- erogeneous graph attention network. In The world wide web conference, pages 2022-2032, 2019.
[42] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete struc- tures for graph neural networks. In International conference on machine learning, pages 1972- 1982. PMLR, 2019.
[43] Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-revised convolutional network. In Machine Learning and Knowledge Discovery in Databases: Euro- pean Conference, ECML PKDD 2020, Ghent, Belgium, September 14-18, 2020, Proceedings. Part III, pages 378- 393. Springer, 2021.
[44] Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in neural information processing systems, 33:19314- 2020.
[45] Ruijia Wang. Shuai Mou, Xiao Wang, Wanpeng Xiao, Qi Ju, Chuan Shi, and Xing Xie. Graph structure estimation neural networks. In Proceedings of the web conference 2021, pages 342- 353, 2021.
[46] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, -1227387-27401, 2022.
[47] Kuan Li, Yang Liu, Xiang Ao, Jianfeng Chi, Jinghua Feng, Hao Yang. and Qing He. Reliable representations make a stronger defender: Unsupervised structure refinement for robust gnn. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 925-99 9355935,222 2022.
[48] Jianan Zhao, Qianlong Wen, Mingxuan Ju, Chuxu Zhang, and Yanfang Ye. Self-supervised graph structure refinement for graph neural networks. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 159-167, 2023.
[49] YIli Sadikaj, Justus Rass, Yllka Velaj, and Claudia Plant. Semi-supervised embedding of attributed multiplex networks. In Proceedings of the ACM Web Conference 2023, pages 578- 587, 2023.
[50] Erlin Pan and Zhao Kang. High-order multi-view clustering for generic data. Information Fusion, 101917 2023,
13

---

[51] Shima Khoshraftar and Aijun An. A survey on graph representation learning methods. ACM Transactions on Intelligent Systems and Technology. 15(1):1-55, 2024.
[52] Liang Liu, Zhao Kang, Jiajia Ruan, and Xixu He. Multilayer graph contrastive clustering network. Information Sciences, 613:256-261 2022.
[53] Liang Peng, Xin Wang, and Xiaofeng Zhu. Unsupervised multiplex graph learning with com- plementary and consistent information. In Proceedings of the 31st ACM International Confer- ence on Multimedia, pages 454 462, 2023.
[54] Cheng Yang, Deyu Bo, Jixi Liu, Yufei Peng, Boyu Chen, Haoran Dai, Ao Sun, Yue Yu, Yixin Xiao, Qi Zhang, et al. Data-centric graph learning: A survey. arXiv preprint arXiv:23 10.04987, 2023.
[55] Jianan Zhao, Xiao Wang, Chuan Shi, Binbin Hu, Guojie Song, and Yanfang Ye. Heterogeneous graph structure learning for graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 4697-4705, 2021.
[56] Ashish Jaiswal, Ashwin Ramesh Babu, Mohammad Zaki Zadeh, Debapriya Banerjee, and Fillia Makedon. A survey on contrastive self-supervised learning. Technologies, 9(1:22 2020.
[57] Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceed- ings of the IEEE/CVF conference on computer vision and pattern recognition, pages 15750- 15758, 2021.
[58] Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simese: Simple contrastive learning of sentence embeddings. In 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, pages 6894-6910. Association for Computational Linguistics (ACL), 2021.
[59] Steffen Schneider, Alexei Baevski, Ronan Collobert, and Michael Auli. wav2vec: Unsuper- vised pre-training for speech recognition. Interspeech 2019, 2019.
[60] Hassan Akbari, Liangzhe Yuan, Rui Qian, Wei-Hong Chuang, Shih-Fu Chang, Yin Cui, and Boqing Gong. Vatt: Transformers for multimodal self-supervised learning from raw video, audio and text. Advances in Neural Information Processing Systems, 34:24206-24221, 2021.
[61] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748-8763 PMLR, 2021.
[62] Yijie Lin, Yuanbiao Gou, Zitao Liu, Boyun Li, Jiancheng Lv, and Xi Peng. Completer: In- complete multi-view clustering via contrastive prediction. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11174-11188 2021.
[63] Marco Federici, Anjan Dutta, Patrick Forré, Nate Kushman, and Zeynep Akata. Learning robust representations via multi-view information bottleneck. In 8th International Conference on Learning Representations, 2020.
[64] Liangjian Wen, Yiji Zhou, Lirong He, Mingyuan Zhou, and Zenglin Xu. Mutual informa- tion gradient estimation for representation learning. In International Conference on Learning Representations, 2020.
[65] Liangjian Wen, Xiasi Wang, Jianzhuang Liu, and Zenglin Xu. Mveb: Self-supervised learning with multi-view entropy bottleneck. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
[66] Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and S Yu Philip. Graph self-supervised learning: survey. IEEE Transactions on Knowledge and Data Engineering. 35(6):5879-590 2022.
[67] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 11015-11023, 2021.
14

---

[68] Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep representations. Journal of Machine Learning Research, 19(50)1-33, 2018.
[69] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. In The Eleventh International Conference on Learning Representa- tions, 2022.
15

---

A
Notations
Table 4: Frequently used notations.
Notation
Description
G. = X}
The 2-th original graph.
Y
The label information.
V,N,dy
The number of graphs/nodes/teauress
A. 11
The adjacency matrix of y-th original graph The shared feature matrix across all graphs. The v-th augmented graph.
X Wxxd
G A X²)
G X
The e-th refined graph.
G X
The learned fused graph.
Hº RVxd,
The node embeddings of the original graph from the graph learner. The node representations of the refined graph of the GCN encoder. The node representations of the fused graph from the GCN encoder. The random masking vector for feature masking. The random masking matrix edge dropping.
2 RAxa
2 RAx
M (U,134
M E (0, 1) NNN
The order of graph aggregation in SGC. The number of layers in GCN.
L
The number of neighhors in ANN.
The pusitive prper-prrreeter in Egen-
GGG
The mutual information between the i-th and j-th refined graphs.
C
The total loss of InfoMGF-RA -R A and InfoMGF-LA.
Eyen
The loss of augmented graph generator in InfoMGF-LA.
@ af-) Berm(-) [+-]
The Hadamard product.
The non-linear activation function.
The Bernuulii distribution.
The concatenation operation.
B Related Work
Unsupervised Multiplex Graph Learning (UMGL). Unlike supervised methods such HAN [41] and SSAMN [49] which rely on label information, UMGL tackles unsupervised tasks in multiplex graphs by using node features and graph structures [50]. Early UMGL methods such MvAGG [38) and MCGC [39] combine graph filtering with unsupervised techniques such as spectral and subspace clustering to uncover underlying patterns in complex networks. With the rise of deep representation
learning [51], UMGL has embraced a new paradigm: Unsupervised learning of low-dimensional node representations using graph neural networks (GNN) [4] and self-supervised techniques [5] for downstream tasks such as node classification, node clustering, and similarity search. O2MAC [26] pioneered the use of GNNs in UMGL, selecting the most informative graph and reconstructing all graph structures to capture shared information. DMGI [2] and HDMI [8] maximize mutual informa- tion between local and global contexts, then fuse representations from different relations. MGCCN [52], MGDCR [9], and BTGF [10] employ various contrastive losses to align representations of diverse relations and prevent dimension collapse. CoCoMG [53] and DMG [3] capture complete in- formation by learning consistency and complementarity between graphs. Despite these advances, critical factor that limits the performance of UMGL is overlooked: the reliability of graph structures. which is the focus of our research.
Graph Structure Learning (GSL). With the advancement of graph neural networks, instead of de- signing complex neural architectures as model-centric approaches, some data-centric research has focused on the graph data itself [54], with graph structure learning (GSL) gaining widespread at- tention for studying the reliability of graph structures. GSL, based on empirical analysis of graph data, recognizes that real-world graph structures are often unreliable, thus opting to learn new struc- tures. GSLB [16] summarizes the general framework of graph structure learning: a Graph Learner takes in the original graph G = {A, X} and generates a refined graph G = {A*, X); then, a Graph Encoder uses the refined graph to obtain node representations or perform class prediction. Consequently, GSL can be broadly categorized into supervised and unsupervised methods based on whether label information is utilized to learn the new structure. For supervised GSL, probabilistic models like LDS [42] and GEN [45] are employed to generate graph structures; GRCN [43], IDGL. [44], and NodeFormer [46] calculate node similarities through metric learning scalable attention
16

---

mechanisms; while ProGNN [11] directly treats all elements in the adjacency matrix as learnable parameters. Meanwhile, methods like SUBLIME [20], STABLE [47]. and GSR [48] introduce self-supervised signals through contrastive learning to learn graph structures without requiring label information. Almost all existing GSL studies concentrate on a single homogeneous graph, with only handful of works such as GTN [18] and HGSL [55] attempting supervised structure learning on heterogeneous graphs containing multiple types nodes. There is still a lack of research concerning more practically significant unsupervised graph structure learning within multiplex graphs.
Contrastive Learning and Information Theory. Contrastive learning, as an effective paradigm of self-supervised learning, enables representation learning without labeled information [56]. It has found widespread applications across various modalities [57-59], particularly effective in multi- view or multi-modal tasks [60-62]. Its theoretical foundation is rooted in multi-view information theory [63, 30, 64]. Standard contrastive learning is based on the assumption of multi-view redun- dancy: shared information between views is almost exactly what is relevant for downstream tasks [17, 23, 24, 65]. They capture shared task-relevant information between views through contrastive pre-training, thus achieving data compression and sufficient representation learning. To successfully apply contrastive learning to multi-modal data with task-relevant unique information, some studies have improved the framework of contrastive learning and extended it to multi-view non-redundancy [17, 28). Recent efforts also attempt to apply contrastive learning to graph learning tasks [66]. They generate contrastive views through graph data augmentation [67] directly utilize different rela- tions within graph data [39]. However, existing multi-view graph contrastive learning still suffers from the limitation of multi-view redundancy, failing extract view-unique task-relevant informa- tion effectively.
C Algorithm and Methodology Details
C.1
Algorithm
Algorithm 1: The optimization of InfoMGF-RA
Input: Original graph structure G {G1 Gy J: Number of nearest neighbors k;; Random masking probability P; Number of epochs E
Output: Learned fused graph G and node representations
Initialize parameters;
Obtain view-specific node features (X! ... XV) by Eq.(1);
3 for e = 1,2,3,..., E do
for each view in {1, V) do
Generate refined graph G {Ag, X} with graph learner by Eq.(1) and
post-processos;
Generate augmented graph G², = { X') with random feature masking and edge dropping:
end
Generate fused graph G {A*,X) with graph learner by (6. and post-processore Obtain node representations {Z²,... .ZV z=" zz Z} through graph encoder GCN; Calculate the total loss by (10) and update parameters in GCN and graph learners;
10
end
12 return fused graph G and node representations Z:
17

---

Algorithm 2: The optimization of InfoMGF-LA
Input:
Original graph structure [GI, Gv): J: Number of nearest neighbors Feature
masking probability p; Hyper- X; Number of epochs E
Output: Learned fused graph G and node representations Initialize parameters;
Obtain view-specific node features {x)... ,X by Eq.(1):
3 for e = 2, ..., do
// Step 1: Fix augmented graphs (G G.y
for each view in (1,....1 V) do Generate refined graph G {A X} with graph learner by Eq.(1) and post-processors;
end
7
Generate fused graph G = {A*, with graph learner by Eq. and post-processors:
Obtain node representations {2] .... Z', Z" z } through graph encoder GCN; Calculate the total loss & by Eq.(10) and update parameters in GCN and graph learners; // Step 2: Fix refined graphs and fused graph {Gi,"" G G*} for each view in f1,...,............... . do
10
11
Generate augmented graph G³, (A, X') with random feature masking and augmented graph generator in Section 3.3
end
Obtain node representations ....... Zv Z" z",.... Zv through graph encoder GCN;
13
Obtain reconstructed features {X- ... XV} through decoder;
15
Calculate Egen by (q.( I) and update parameters in augmented graph generator and decoder;
end
17
return fused graph G and node representations Z;
C.2 Complexity Analysis
First, we analyze the time complexity of each component InfoMGF. In this paragraph, let V. N, and m represent the numbers of graphs, nodes, and edges, while by and by denote the batch sizes the locality-sensitive k NN and contrastive loss computation. The layer numbers of graph learner, graph encoder GCN, and non-linear projector are denoted L,, Lg, and L.z, respectively. The feature, hidden layer, and representation dimensions are denoted as dy, da. and d, respectively. We analyze the complexity of ANN and GCN in scalable versions. Be- fore training, scalable SGC is applied with a complexity of O(Vmrdy) related to the aggrega- tion order r. During training, we first perform graph learner with scalable NN that requires O(VN Lıd, + Vb) For the GCN encoder and non-linear projector, the total complexity is O (VmL2d4 + V md + L2dh + VVNd, (d dy) L3dd). Within the graph augmentation module, the complexity feature masking O(Nd,). The learnable generative graph augmenta- tion in InfoMGF-LA has a complexity of O(VNdyd, terms are contributed by the augmented graph generator and the last one is for the decoder. For InfoMGF-RA, the random edge drop requires O(Vm) m) time complexity. For the loss computation, the complexity is OVV
Vmnd, V VNddd), where the first two
To simplify the overall complexity, denote the larger terms within L1, L2, and L3 L, the larger terms between d2 and d as d, the larger terms between b, and by B. Since the scalable SGC operation only needs to be performed once before training, its impact on training time is negligible. Therefore, only consider total complexity during the training process. The overall complexity of both InfoMGF-RA and InfoMGF-LA OVV m/L++ N Ld VV V vd)). which is comparable to the mainstream unsupervised GSL models, including our baselines. For example, SUBLIME [20] needs be trained on each graph in a multiplex graph dataset, and its time complexity is O(VmLd V N L + VVd (1 L.) V B(d d)), which only has a slight difference in the last term compared to the time complexity of our method.
18

---

C.3 Details of Post-processing Techniques
After constructing the cosine similarity matrix of H we employ the postprocessor to ensure that A is sparse, nonnegative, symmetric and normalized. For convenience, we omit the subscript v in the discussion below.
NNN for sparsity. The fully connected adjacency matrix usually makes little sense for most applica- tions and results expensive computation cost. Hence, we conduct the k-nearest neighbors (kNN) operation to sparsify the learned graph. We keep the edges with top-k values and otherwise to 0 for each node and get the sparse adjacency matrix A
Symmetrization and Activation. As real-world connections are often bidirectional, we make the adjacency matrix symmetrie. Additionally, the weight of each edge should be non-negative. With the input A they can be expressed as follows:
A stym (AA))) + (
(12)
2
where (-) is a non-linear activation implemented by the ReLU function.
Normalization. The normalized adjacency matrix with self-loop can be obtained as follows:
A (D A (ñoum)-
(13)
where Deam is the degree matrix of A with self-loop. Afterward, we can obtain the adjacency matrix A for each view, which possesses the desirable properties of sparsity, non-negativity, sym- metry, and normalization.
C.4 Details of Loss Functions
For each view and j. the lower and upper bound of ((2'; in (8) and Eq.(9) can be calculated for the node
eimml 2% 21 3/To
la A Tim)) log
(14)
nn= mimm 7: RT/
labl Lin. 22n) sim( /T
sim 7im. 2/3//es
(15)
N
where 7: is the non- non-linear projection of Zi through MLP, sim(-) refers to the cosine similarity and T the temperature parameter in contrastive loss. The loss L, is computed as follows:
V
V
N
Σ C. = NV(V == m=1
ΣΣ
7 + e0o Tin Z,
(16)
Likewise, compute Ly and L. in the total loss L with the same approach. Upon optimizing L. our objective also entails the minimization of Lgens which incorporates A Ly (here we compute Cu using the upper bound) and the loss term of the reconstruction. Egen can be represented by:
V
N
N
(X)TX8
) (17)
ggen
x
1
Σ
Σ
2,)
2NV
NV
|x3|| (
am
D Proofs of Theorems
D.1 Properties of multi-view mutual information and representations
In this section, we enumerate some basic properties of mutual information used to prove the theo- rems. For any random variables z, and we have:
(Pi) -en-nigat:
(xx 2 0, 0.1(2:2)2) 2
(18)
19

---

(P2) Chain rule:
[x, yt 2) [y; 2) (0;
(19)
(Ps) Chain rule (Multivariate Mutual Information):
[x: 2) = [(y; (3: 2|2)
(20)
We also introduce the property of representation:
Lemma 1. /63, 68) If z a representation o, then: v,
[z; a/v, b)
(21)
for any variable (or groups of variables) and b in the system. Whenever random variable is defined as a representation of v, we state that is conditionally independent of any other variable in the system given This does not imply that must be deterministic function of c. but rather that the source of z stochasticity is independent of the other random variables.
D.2 Proof of Proposition
Proof of Proposition 1: Due to each G is obtained from G; through deterministic function, which independent of other variables. Thus, here G can be regarded as a representation of G.. For any two different views G; and Gj. we have:
GG PP:)
=' C)
(22)
C ((G]:G)
where follows from Lemma The bound reported in this equation tight when I G2 0, this happens whenever G contains all the information regarding G (and therefore C,). Symmet- rically, we can also prove (G]; G.) 2 [(G;; Gj). then we have
I(G;; G,) [GG] G.) 2I(G;
(23)
Proposition holds.
D.3 Proof of Theorem
Proof of Theorem I. From the definition of optimal augmentation graph, we have
T(G'; G.) = I(Y; G,)
(24)
Similar to the proof of Proposition I, as G is regarded representation of G,, therefore:
IG;; G.) =
(25)
IG;
(26)
Based on (24) and the above equations, then
IG;; = I(G,; (G)
Eq-(26) -GG
Eq.(2) ((G [G;
(27)
(P) [(GRY;
Bg +
(P) Y(G;Y)
It shows that maximizing [G;;; G.) and maximizing [ Y) are equivalent. Theorem holds.
20

---

D.4
Proof of Theorem 2
Proof of Theorem 2. Here we theoretically compare [[G]; with [GG G
Discussion For I Gi). we have:
T(G;; G.) T[G
- -G G.) (IGGG)))++ I(G;
(28)
In the process of maximizing ; Gi). not only is task-relevant information (the first term) maxi- mized, but task-irrelevant information (the second term) is also maximized.
Discussion 2. For (G;; G)),, based on Theorem we have:
[[ G.) Y)
(29)
Obviously, task-irreeevant information is maximized. Theorem holds.
D.5 Proof of Theorem 3
Proof of Theorem 3. To prove the theorem, we need to use the following three properties of entropy:
(H1) Relationship between the mutual information and entropy:
[z: v) H (xly)
(30)
(H2) Relationship between the conditional entropy and entropy:
H H(. v) (v)
(31)
(Hz) Relationship between the conditional mutual information and entropy:
[x:; v| = H(])²) - Hx
(32)
By maximizing the mutual information with each refined graph, the optimized fused graph G would contain all information from every G. For any Gj, we denote G as the fused graph all views except view Thus have:
H(G*) = (G) H(G))))) + ((G;:))
(33)
where (G) and H G;; indicate the specific information of G and G respectively, and I[G G indicates the consistent information between G and G;-.
Then we have:
H(G = H +IG
HGG HC H(G)) -
(34)
H(G + G
HGG G.
Therefore, for any downstream task Y, we further have:
H(G Y) H(G G.
(35)
Based on the properties of mutual information and entropy, we can prove:
I();Y) H(G*) HHG"lY)
HH(G") - -H(
(36)
(3.(34) H(G G;) H G) H(Y)
Based on the properties of entropy, we have the proofs as follows:
IGG; H(G)) HG
(37)
21

---

TG (G H,
(38)
= HC G2) -(G))-H(GGG,)
With the equations above, we can obtain
T(GYY) - -ICHH
-
(a)) H(G;, G.) H(Y)) H(G,, G, Y)
H(G C.) + H(Y) -
(39)
According to (36) and (39), we have:
Y = ( +
(40)
As T Y G 2 0 (P)), then can get
T(G;;) 2 Y)
(41)
Similarly, we can also obtain
I(G"YY) > Y)
(42)
As (41) holds for any i, thus
T(G 2 max [G;; Y).
(43)
Theorem holds.
E
Experimental Settings
E.1
Datasets
We consider benchmark datasets in total. The statistics of the datasets are provided in Table 5. Through the value of "Unique relevant edge ratio", we can observe a significant amount of view- unique task-relevant information present in each real-world multiplex graph dataset. should be noted that MAG is subset of OGBN-MAG [36], consisting of the four largest classes. This dataset was first organized into current subset version in the following paper [1].
Table 5: Statistics of datasets.
Nodes
Relation type
Edges
Uniqu edge (%)
Classes
Training
Validution
ACM
3,025
Puper Subject Poper (PSP)
Pegen-AuthhntPipee (PAP)
2,197.556
26,416
99.05
1,902
300
2.125
DBLP
2,957
Author-Papes Caatnn-Pppe---oofffee Contferenceeeeeee SacuuffsenncePape---aae Paper-Attiox (APCPA)
Author Puper Author (APA)
1,460,224
2,398
99.82
600
300
2,057
Business User Dusiness (DUB)
$25,718
83.12
Yelp
2,614
Business- Service- Business Service-Bussiiess (BS8)
2,475.108
97.49
3
300
300
2,014
Business Rating Busine- (B1
1,484,6922
93.07
MAG
Pager-Autor-Pppee
Paper- (PP)
10,067.799
1,806.296
64.59
40,000
10,000
63,919
E.2 Hyper-parameters Settings and Infrastructure
We implement all experiments the platform with PyTorch 1.10.1 and DGL 0.9.1 using Intel(R) Xeon(R) Platinum 8457C 20 vCPU and an L20 48GB GPU. We perform 5 runs of all experiments and report the average results. In the large MAG data set, InfoMGF-RA takes 80 minutes to complete 5 runs, whereas, on other datasets, both versions of InfoMGF require less than 5 minutes.
Our model is trained with the Adam optimizer, and Table 6 presents the hyper- parameter settings on all datasets. Here, E represents the number of epochs for training, and Ir denotes the learning rate. The hidden-layer dimension dj and representation dimension d of graph encoder GCN are tuned from (32, 64, 128, 256). The number of neighbors for ANN searched from (5, 10, 15, 20, 30). The order of graph aggregation r and the number of layers T. in GCN are set to 2 or 3, aligning with
22

---

Table 6: Details of the syper-parameter: settings,
Random Aug.
Generative Aug.
Dataset
E
Ir
da
d
k
Ps
Irgen
ACM
100
0.01
128
15
0.5
0.2
0.5
0.001
0.01
DBLP
100
0.01
64
10
0.5
0.2
0.5
0.001
Yelp
100
0.001
128
15
0.2
0.5
0.001
MAG
200
0.005
256
15
0.2
0.5
the common layer count of GNN models [69]. The probability p of random feature masking is set to 0.5 0, and the temperature parameter т. in contrastive loss is fixed 0.2. For InfoMGF-RR using random graph augmentation, the probability Ps of random edge dropping is fixed at 0.5. For InfoMGF-LA with learnable generative graph augmentation, the generator's 's learning rate Ir gen is fixed at 0.001, the temperature parameter т in Gumbel-Max is set to 1, and the hyper-parameter controlling the minimization of mutual information fine-tuned from {0.001, 0.01, 0.1, 10). For the large dataset MAG, we compute the contrastive loss for estimating mutual information in batches, with a batch size 2560.
Additional Experiments
F1 Sensitivity Analysis
We analyze the impact of two important hyper- syper-parameters: the number of neighbors i in kNN and hyper-parameter À controlling the influence of mutual information minimization to generate aug- mented graphs. The performance change of InfoMGF-LA with respect to k illustrated in Figure 6a. Overall, InfoMGF shows low sensitivity to changes in k. The model achieves optimal perfor- mance when set to 10 or 15. However, when very small (k 5), detrimental effects may arise, possibly due to the limited number of beneficial neighbors. As & increases, the performance can still be maintained high. Figure 6b shows the results to À from {0.001, 0.01,0.1,11. Our proposed model shows low sensitivity to changes in À in general, while the À corresponding to achieving the best performance varies across different datasets.
F.2 Graph Visualization
Figures 7 and 8, respectively, present the visualizations of the subgraph adjacency matrices of the original multiplex graphs and the learned fused graph G on the DBLP and Yelp datasets. In DBLP, the two categories are machine learning (CI) and information retrieval (C2), while in Yelp, the cat- egories are Mexican flavor (CI) and hamburger type (C2). can be observed that G not only removes the inter-class edges in the original structure but also retains key intra-class edges with weights, not just the shared edges. This further demonstrates the effectiveness of InfoMGF in elimi- nating task- -ireeeeeeeeant noise while preserving sufficient resk-relevant information.
94
93
Macro-F1 (%6)
Macro-F111 (9%)
92
91
91
ACM
ACM
DBLP
DBLP
Yelp
89
10
20
30
40
0.001
0.01
10
Number of neighbors k
A
(a) The influence
(b) The influence A.
Figure 6: Additional experiments on sensitivity analysis.
23

---

3
D
C1
C1
C1
APA
(b) APCPA
(c)
C
Figure 7: Heatmaps of the subgraph adjacency matrices of the original and learned graphs on DBLP.
(a) BUB
(b) BSB
(c)
BLB
(d) G*
Figure 8: Heatmaps the subgraph adjacency matrices the original and learned graphs on Yelp.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All our main works and contributions are included in the introduction part, Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of work are discussed in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings,

---

model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Our assumptions, theorems, and their proofs are provided in Appendix D. Besides, properly reference the theorems which have been proven.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
All experimental setups and details of hyper-parameters are in Appendix E.2.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
25

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, deseribing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors welcome describe the partieular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code and data of our research released through Github link, which can be found in our abstract.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.c cc/
for more details.
While we encourage the release of code and data, understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: cubblic/guides
/nips.
CrodeSubmissionna.
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
26

---

Answer: [Yes]
Justification: Experimental details and other supplements are summarized in Appendix E.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The experimental results with standard deviation for our method and baselines are presented in Table 2.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the eтror bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of eπrоrs is not verified.
For asymmetric distributions, the authors should careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computer resources used in our experiments including compute workers, memory, and execution time are provided Section E.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't it make it into the paper).
27

---

9. Code Of Ethics
Question:
Does the research conducted in the paper conform, in every respect, with the
NeurIPS Code of Ethics https: httpp::///eurrss..co
Answer: [Yes]
Justification: anonymity.
We have reviewed the NeurIPS Code of Ethics and ensure to preserve
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: A new problem on the reliability of real-world multiplex graph structures is proposed in our paper. The broader impacts of our work lie in the contributions promote the development of the graph learning community, summarized the introduction part.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses no such risks, however, we still take this into account.
Guidelines:
The answer NA means that the paper poses such risks.
28

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer:
[Yes]
Justification: Only released datasets are used our paper. We cite the original paper in the Section 4.1.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, saperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: Code for our model is provided through Github link. Explanations for our research and code are provided in an explanatory document the GitHub repository.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "iXj0tm8q3t", "reviewer": "Reviewer_2Joh", "summary": "The authors develop a novel approach to improve Unsupervised Multiplex Graph Learning by refining graph structures to eliminate noise and maximize relevant information. The method utilizes mutual information maximization to integrate multiple graph views effectively. Theoretical validation and comprehensive experiments show that the proposed method outperforms existing methods.", "questions": "1.\tIs there any explanation about why the method performs better on clustering than classification?\n2.\tHow to solve the above issue?\n3.\tThe font of k in the caption of fig.5a is not correct. \n4.\tIn the Appendix, the authors proof Proposition 1, however, there is no corresponding one in the main paper.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tMultiplex graph provides an efficient representation of complex systems. This paper focuses on non-redundancy issue, which is a new perspective and opens up a new avenue for future research.\n2.\tThe proposed method adopts an unsupervised and generalized approach. Its performance surpasses several supervised approaches, underscoring its potential for practical applications. \n3.\tThe framework’s performance is validated through comprehensive experiments and compared with more than 20 methods.\n4.\tVisualization is also a strong point of this paper. The figures of node correlation, heatmaps of the subgraph, and unique relevant edge ratio are very illustrative.", "weaknesses": "1.\tAccording to Table 1 and 2, it seems that the proposed method improves more on clustering than classification.\n2.\tOverall, this paper is well-organized. However, the writing could be improved in terms of tone and words.\n3.\tThere are too many notations, which are confusing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful feedback. Your constructive criticism is invaluable in refining our work. Below, we give point-by-point responses to your comments.\n\n**Q1 & W1 & Q2. According to Table 1 and 2, it seems that the proposed method improves more on clustering than classification. Is there any explanation about why the method performs better on clustering than classification? How to solve the above issue?**\n\nThanks for your concern. Your observations are accurate and well-founded. The bigger improvement of our method in clustering  compared to classification can be attributed to the following factors:\n\n1. **Differences in Baselines**: In the clustering task, we primarily compare our method against unsupervised multiplex graph learning (UMGL) methods. As summarized in the Introduction, existing UMGL methods are graph-fixed, which means they struggle to handle real-world noisy graph data. In contrast, for a comprehensive evaluation, we compare our method against a wide range of supervised/unsupervised single graph structure learning (GSL) methods in the classification task. These GSL methods refine the graph structure, leading to better baseline performances. This partially explains the substantial improvement in clustering compared to classification.\n2. **Incorporating Pre-trained Knowledge**: In the clustering task, we evaluate the node representations $Z$ of the learned fused graph by K-means. Notably, $Z$ not only contains information from the learned fused graph but also incorporates ample pre-trained knowledge from the GCN encoder parameters. This pre-trained knowledge contains more underlying information inside multiplex graph data, thereby enhancing node clustering performance. However, in the classification task, we retrain a new GCN on the learned fused graph to align with existing GSL paradigms, which means that the classification performance reflects only the quality of the learned graph and lacks the richer pre-trained knowledge. This also explains why the improvement in classification is smaller compared to clustering.\n\n**Future Approaches**: In the future, we will leverage transfer learning to migrate pre-trained knowledge to a broader range of downstream tasks, including classification. For instance, we can initialize the classifier for classification tasks using pre-trained GCN parameters and fine-tune it to improve the performance. Additionally, we will also explore cross-domain transfer learning, enhancing our method’s out-of-distribution detection and generalization capabilities for handling real-world graph data. Furthermore, we will delve into multiplex graph structure learning in supervised or semi-supervised scenarios. By leveraging annotated information, we aim to improve the quality of the learned graphs.\n\n\n\n**W3. There are too many notations,  which are confusing.**\n\nSorry for the trouble caused by our symbols, we agree that too many notations would confuse the readers. Hence, we summarize frequently used notations in our paper as a **Table** in the PDF file of the Global Author Rebuttal. Meanwhile, we also explain some important symbols in the following:\n\n1. **Graph symbols.** Such as $G_v=\\\\{A_v,X\\\\}$, $G^s_v=\\\\{A_v^s,X\\\\}$, and $G^{\\prime}_v=\\\\{A_v^{\\prime},X^{\\prime} \\\\}$ to denote the original, refined, and augmented $v$-th graph respectively. The learned fused graph is denoted as $G^s=\\\\{A^s,X\\\\}$. It is worth noting that $A^s$ and all $A^s_v$ are generated via the graph learner.\n2. **Vectors and matrices used in graph learning.** Most notations appear in the graph learning stage, for instance, we use $X_i^{v}$ to denote the view-specific feature of $i$-th node in $v$-th graph. $H^v$ is the node embeddings of the $v$-th original graph in graph learner, which is used to generate the refined graph. $Z^{v}=\\mathrm{GCN}(A_{v}^{s}, X)$ is the node representations of the $v$-th refined graph in the GCN encoder, which is used for the loss calculation. It is obvious that these notations cannot be omitted for their diverse utilizes.\n3. **Units for optimization.** During optimization, we introduce the mutual information lower/upper bound and loss function, which combine the aforementioned notations. Superscripts and subscripts are important for distinguishing different views and different nodes.\n\nWe will include the “Frequently Used Notations” table and explanations of the symbols in the Appendix. Thanks for your constructive suggestion.\n\n\n\n**Q3.  The font of k in the caption of fig.5a is not correct.**\n\nSorry for the mistake we made. We will make corrections on this issue in the final version of our paper. And we will conduct a thorough review of the paper to ensure there are no typographical or language errors.\n\n\n\n**Q4. In the Appendix, the authors proof Proposition 1, however, there is no corresponding one in the main paper.**\n\nThank you for your valuable feedback. We will incorporate the corresponding proposition into the main paper, which will make our theoretical focus clearer and more prominent.\n\nOnce again, we sincerely appreciate your time and effort in reviewing our paper. Your constructive criticism has been invaluable in refining our work, and we are more than happy to add clarifications to address any additional recommendations and reviews from you!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5J0sqL1ri5", "reviewer": "Reviewer_cF8g", "summary": "The paper introduces InfoMGF, an innovative framework for Unsupervised Multiplex Graph Learning (UMGL) that addresses the often-overlooked issue of graph structure reliability. InfoMGF refines graph structures by removing task-irrelevant noise and maximizing task-relevant information through mutual information maximization. Extensive experiments demonstrate its superior performance over various baselines and even some supervised methods, validating its effectiveness in enhancing node representation learning.", "questions": "1.\tThere are some small errors in Algorithm 1. In particular, the title of it is InfoMGF-LA, however, line 11 also includes the operation for InfoMGF-RA.\n2.\tThe proposed method depends on the assumption of optimal augmentation. How to guarantee that the used feature and structure augmentations are optimal? It is still unclear to me.\n3.\tThe authors discuss the robustness against structure noise. How about feature noise? Could you share your intuition on this matter?", "limitations": "The paper discusses the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- New Problem Formulation: The paper pioneers the investigation of graph structure reliability in multiplex graphs, which is a significant advancement in the field. Multiplex graphs enrich the representation of real-world systems and its analysis is very difficult inherently.\n- Theoretical Analysis: The several theorems are quite interesting and provide a solid foundation for the proposed method. In particular, Theorem 3 proves the necessity of fusing multiplex graphs.\n- Extensive Evaluation: The framework is thoroughly tested against various state-of-the-art methods on both node clustering and classification tasks, showcasing its robustness and effectiveness across different tasks. The comparison methods are representative and new.", "weaknesses": "- Robustness: Fig.4 shows that the proposed method is very robust to structure noise. However, more analysis is needed. Both InfoMGF and SUBLIME are structure learning methods. Compared to InfoMGF，Why does the performance of SUBLIME degrade rapidly in the case of edge deletions?\n- Clarity: The paper develops two algorithms in this paper: InfoMGF-RA and InfoMGF-LA. However, it is a little confusion that what is the difference in their objective functions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful feedback. Your constructive criticism is invaluable in refining our work. Below, we give point-by-point responses to your comments.\n\n**W1. Fig.4 shows that the proposed method is very robust to structure noise. However, more analysis is needed. Both InfoMGF and SUBLIME are structure learning methods. Compared to InfoMGF. Why does the performance of SUBLIME degrade rapidly in the case of edge deletions?**\n\nAs you can see in Fig.4, our model is significantly more robust than SUBLIME when deleting edges. This can be attributed to the following factors:\n\n1. When edges are deleted, the task-relevant information contained in the graph tends to decrease. SUBLIME, as a single graph method, cannot fully leverage the task-relevant information from different graphs. In contrast, InfoMGF considers multiplex graph non-redundancy, enabling it to capture both shared and unique task-relevant information from all graphs. Consequently, when the edge deletion ratio is substantial, InfoMGF outperforms SUBLIME significantly.\n2. Fig.4 shows the robustness comparison between InfoMGF-LA and other methods. Compared to existing methods (including SUBLIME) that use random graph augmentation, the novel learnable generative augmentation used in InfoMGF-LA is more reliable and interpretable. This approach retains more task-relevant information while reducing irrelevant noise. As a result, our method is more robust across various scenarios.\n\n**W2 & Q1. The paper develops two algorithms in this paper: InfoMGF-RA and InfoMGF-LA. However, it is a little confusion that what is the difference in their objective functions. There are some small errors in Algorithm 1. In particular, the title of it is InfoMGF-LA, however, line 11 also includes the operation for InfoMGF-RA.** \n\nWe apologize for any confusion. InfoMGF-RA and InfoMGF-LA have the same optimization objective (Equation 10), with the primary difference lying in the generation of augmented graphs. Graph augmentation includes both feature and structure augmentation. Notably, both RA and LA use simple yet effective random feature masking for feature augmentation. However, for structure augmentation, RA and LA employ random edge dropping and learnable generative augmentation, respectively. For InfoMGF-RA, both feature and structure augmentations are non-parametric methods, so its overall objective is Equation 10. In contrast, InfoMGF-LA requires to train the learnable generative augmentation module (optimized by Equation 11). Therefore, we propose an **alternating optimization strategy** to iteratively optimize the total model loss ($\\mathcal{L}$) and the augmented graph generator loss ($\\mathcal{L}_{gen}$), which is described in lines 233-237 of our paper.\n\nRegarding your question about Algorithm 1, there seems to be a misunderstanding. Since InfoMGF-LA also requires random feature masking to generate augmented features, the description in Algorithm 1 is accurate. To make the distinction between InfoMGF-RA and InfoMGF-LA clearer, we will include the algorithm for InfoMGF-RA in the final version.\n\n**Q2. The proposed method depends on the assumption of optimal augmentation. How to guarantee that the used feature and structure augmentations are optimal?**\n\nIn fact, due to the unsupervised setting where label information is unavailable, obtaining rigorously theoretically guaranteed $G_v^\\prime$ remains challenging. Therefore, we have to approach optimal augmentation from a practical perspective.\n\nPrevious research often uses random augmentation, assuming that most of the perturbed information is task-irrelevant. Additionally, existing methods commonly augment features and structures simultaneously, as both typically contain rich task-relevant information. In contrast, our approach takes further steps:\n\n1. **Feature Augmentation**: We continue to employ simple yet effective random feature masking. Extensive pretraining studies in graph learning [1], CV [2], and NLP [3] have demonstrated that random masking performs remarkably well when augmenting information-dense data, without requiring intricate techniques.\n2. **Structure Augmentation**: Random edge dropping may lack reliability and interpretability, so we propose the learnable generative augmentation, which implements edge-wise probability modeling in the original graphs. To effectively train the augmented graph generator, we design the loss function $\\mathcal{L}_{gen}$ based on **the principle of optimal augmentation**. The reconstruction term constrains the augmented graph to retain essential information, while the mutual information minimization term aims to reduce irrelevant noise within the augmented graph. We delve into the optimization process and advantages of our proposed augmentation in the relevant section of our paper (lines 183-198).\n\nIn summary, due to the unavailability of label information in unsupervised tasks, we cannot achieve rigorously theoretically guaranteed augmentation. Nevertheless, we adhere to the principle of optimal augmentation to develop learnable generative augmentation and its optimization objectives. Extensive experiments further validate the effectiveness of our approach.\n\n[1] \"Graph Contrastive Learning with Augmentations.\" NeurIPS (2020).\n\n[2] \"Masked Autoencoders Are Scalable Vision Learners.\" CVPR (2022).\n\n[3] \"UniLMv2: Pseudo-Masked Language Models for Unified Language Model Pre-Training.\" ICML (2020).\n\n\n**Q3. The authors discuss the robustness against structure noise. How about feature noise? Could you share your intuition on this matter?**\n\nFollowing your advice, we add some additional experiments on this issue, where the experimental results and analysis are in the PDF file of the Global Author Rebuttal.\n\nOnce again, we sincerely appreciate your time and effort in reviewing our paper. Your constructive criticism has been invaluable in refining our work, and we hope these adjustments and explanations can address your concerns satisfactorily.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hTcRDf1kRZ", "reviewer": "Reviewer_ei6T", "summary": "The paper introduces InfoMGF (Information-aware Unsupervised Multiplex Graph Fusion), a novel framework aimed at addressing the issue of graph structure reliability in Multiplex Graphs. The primary goal is to refine graph structures to eliminate noise and maximize task-relevant information. Theoretical analysis and comprehensive experimental results validate its effectiveness.", "questions": "As above.", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tOriginality: The paper addresses a critical gap in Unsupervised Multiplex Graph Learning (UMGL) by focusing on the reliability of graph structures, which is often overlooked in existing research.\n2.\tQuality: The proposed InfoMGF framework effectively refines graph structures to eliminate noise and maximizes both view-shared and view-unique task-relevant information. Theoretical analyses provided in the paper validate the effectiveness of InfoMGF in capturing task-relevant information and improving graph fusion. Extensive experiments demonstrate that InfoMGF outperforms various baselines and even sophisticated supervised approaches in different downstream tasks.\n3.\tClarity: The paper is generally clearly written and well organized.", "weaknesses": "1.\tScalability: The framework involves several steps. Though the paper provides the complexity analysis in Appendix for each step, it is still unclear what is the overall complexity.\n2.\tReproducibility: The authors share the code for reproducibility. However, I didn’t see the datasets.\n3.\tAccuracy: The authors should check for the few grammatical and spelling errors that occur in the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful feedback. Your constructive criticism is invaluable in refining our work. Below, we give point-by-point responses to your comments.\n\n1. **Scalability: The framework involves several steps. Though the paper provides the complexity analysis in Appendix for each step, it is still unclear what is the overall complexity.**\n\n We apologize for the unclear and incomplete description of the time complexity. We will revise the time complexity analysis and include the overall complexity. Here is the revised version:\n\nWe first analyze the time complexity of each component in InfoMGF. In this paragraph, let $V$, $N$, and $m$ represent the numbers of graphs, nodes, and edges, while $b_1$ and $b_2$ denote the batch sizes of locality-sensitive $k$NN and contrastive loss computation. The layer numbers of graph learner, graph encoder GCN, and non-linear projector are denoted as $L_1$, $L_2$, and $L_3$, respectively. The feature, hidden layer, and representation dimensions are denoted as $d_f$, $d_h$, and $d$, respectively. We analyze the complexity of $k$NN and GCN in scalable versions. Before training, scalable SGC is applied with a complexity of $\\mathcal{O}(Vmrd_f)$ related to the aggregation order $r$. During training, we first conduct a graph learner with scalable $k$NN requiring $\\mathcal{O}(VNL_1d_f+VNb_1d_f)$. For the GCN encoder and non-linear projector, the total complexity is $\\mathcal{O}\\left(VmL_2d_h+Vmd+VNL_2d_h^2+VNd_h(d+d_f)+VNL_3d^2\\right)$. Within the graph augmentation module, the complexity of feature masking is $\\mathcal{O}(Nd_f)$. The learnable generative graph augmentation in InfoMGF-LA has a complexity of $\\mathcal{O}(VNd_fd_h+Vmd_h+VNd_fd)$, where the first two terms are contributed by augmented graph generator, and the last one is for the decoder. For InfoMGF-RA, the random edge dropping requires $\\mathcal{O}(Vm)$ time complexity. For the loss computation, the complexity is $\\mathcal{O}(V^2Nb_2d)$.\n\nTo simplify the overall complexity, we denote the larger terms within $L_1$, $L_2$, and $L_3$ as $L$, the larger terms between $d_h$ and $d$ as $\\hat{d}$, the larger terms between $b_1$ and $b_2$ as $B$. Since the scalable SGC operation only needs to be performed once before training, its impact on training time is negligible. Therefore, we only consider the total complexity during the training process. The overall complexity of both InfoMGF-RA and InfoMGF-LA is: $\\mathcal{O}(VmL\\hat{d}+VNL\\hat{d}^2+VNd_f(\\hat{d}+L)+VNB(d_f+V\\hat{d}))$, which is comparable to mainstream unsupervised GSL models, including our baselines. For example, SUBLIME [1] needs to be trained on each graph in a multiplex graph dataset, and its time complexity is: $\\mathcal{O}(VmL\\hat{d}+VNL\\hat{d}^2+VNd_f(\\hat{d}+L)+VNB(d_f+\\hat{d}))$, which only has a slight difference in the last term compared to the time complexity of our method.\n\n[1] Liu et al. \"Towards Unsupervised Deep Graph Structure Learning.\" WWW (2022).\n\n\n\n2. **Reproducibility: The authors share the code for reproducibility. However, I didn’t see the datasets.**\n\nAt the end of the abstract, there is a link to an Anonymous GitHub repository that contains the complete code for our method. All the used multiplex graph datasets are publicly available, and we have included the corresponding references for each dataset. We will release all the datasets after acceptance and include them along with the complete code in the GitHub repository.\n\n3. **Accuracy: The authors should check for the few grammatical and spelling errors that occur in the text.**\n\nWe will carefully review and correct any grammar and spelling errors in the manuscript. We focus on improving the clarity and coherence of our writing while ensuring language accuracy.\n\nOnce again, we sincerely appreciate your time and effort in reviewing our paper. Your constructive criticism has been invaluable in refining our work, and we hope these adjustments and explanations could address your concerns satisfactorily.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h6c9IXNyB5", "reviewer": "Reviewer_gjsJ", "summary": "- This paper presents an information theory approach to obtain a single graph fused from a multiplex graph, which preserves \n   - sufficient task-relevant information \n   - while removing task-irrelevant noise. \n- A learnable graph augmentation strategy is also developed. \n   - The learned graph and representation can be applied to different types of tasks. \n- The effectiveness is supported by extensive experimental results.", "questions": "I list them in **Weaknesses**.", "limitations": "Some imitations are addressed in $\\S5$.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is well-motivated. \n   - The authors find that each graph contains much unique task-relevant information, which is ignored by mainstream contrastive learning-based methods.\n- This paper develops multiple graphs non-redundancy principle, which lays the foundation for multiplex graph data process. \n   - Two random and generative graph augmentation strategies are accordingly built to capture view-unique task information.\n- The experimental results are promising. \n   - The framework demonstrates a clear advantage over existing methods, including advanced supervised approaches, highlighting its potential for broad application.\n- This paper provides the code and all experimental settings for reproducing the results.", "weaknesses": "- The difference between the existing non-redundancy principle and multiplex graph non-redundancy is unclear. Please clarify it.\n- The proposed InfoMGF-LA runs out-of-memory on MAG data. The reason should be given.\n- It is possible that the proposed method cannot handle real-world large-scale graph. It should be addressed in the future and discussed in the conclusion part.\n- The difference between the proposed method and DGM is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful feedback. Your constructive criticism is invaluable in refining our work. Below, we give point-by-point responses to your comments.\n\n1. **The difference between the existing non-redundancy principle and multiplex graph non-redundancy is unclear. Please clarify it.**\n\nThe primary distinction between multiplex graph non-redundancy and existing non-redundancy principles lies in our consideration of the complexity and uniqueness of graph-structured data. Existing work mainly focuses on non-redundancy in bimodal/view data of images and texts [1], considering that different views may have unique task-relevant information. For image and text data, the non-redundancy is intuitively easy to understand and verify. However, real-world graph data is often complex and not intuitive, making the analysis of non-redundancy very tricky and difficult. Therefore, we propose the concept of \"The Unique Relevant Edge Ratio\" and conduct empirical research, creatively explaining the non-redundant properties of graph data from a structural connectivity perspective. Furthermore, this also demonstrates that relying solely on decoupled node representation learning is insufficient for capturing both shared and task-specific information in multiplex graphs; graph structure refinement or relearning is necessary.\n\n[1] Liang et al. \"Factorized Contrastive Learning: Going beyond Multi-view Redundancy.\" NeurIPS (2023).\n\n2. **The proposed InfoMGF-LA runs out-of-memory on MAG data. The reason should be given.**\n\n As a large-scale real-world multiplex graph dataset, MAG’s PAP graph contains a substantial number of edges—10,067,799 to be precise. The primary reason InfoMGF cannot be successfully trained lies in its use of learnable generative augmentation, which necessitates probabilistic modeling of each edge in the original graphs (Equation 4 of our paper). During model optimization, the weight of each edge contributes to gradient calculations.  The significant memory requirements render InfoMGF-LA impractical for training on MAG data. Despite this limitation, our alternative approach, InfoMGF-RA, still achieves remarkable performance. We believe that this outcome underscores the efficacy of our method.\n\n3. **It is possible that the proposed method cannot handle real-world large-scale graph. It should be addressed in the future and discussed in the conclusion part.**\n\nWe appreciate your concern regarding the scalability of our method. We will include a discussion on scalability in Section 5 “Conclusion and Limitation,” which will make our contributions and limitations more complete and accurate. To enable InfoMGF-LA to handle real-world large-scale graph data successfully, we will focus on developing scalable and learnable graph augmentation methods to replace the existing edge-wise probability modeling augmentation. According to current research [2], most deep graph generation methods still cannot escape the complexity of $\\mathcal{O}(N^2)$ or $\\mathcal{O}(\\vert E\\vert)$, making them unsuitable for large-scale graph data. This issue becomes even more challenging when considering node attribute information. In the future, we may explore using diffusion-based generative models to address large graph augmentation or generation.\n\n[2] Zhu et al. \"A Survey on Deep Graph Generation: Methods and applications.\" LOG (2022).\n\n4. **The difference between the proposed method and DGM is unclear.**\n\nThe main difference between InfoMGF and DMG [3] lies in the task objectives and potential applicability. Specifically, we aim to address the reliability of multiplex graph structures by leveraging unsupervised graph structure learning to preserve task-relevant information while removing task-irrelevant noise. In contrast, DMG is a graph-fixed method that focuses solely on node representation learning. This limitation prevents DMG, and similar graph-fixed methods, from effectively handling noisy real-world graph data. InfoMGF, as a data-centric GSL framework, can achieve both graph structure refinement and representation learning, highlighting its broader range of potential applications.\n\n[3] Mo et al. \"Disentangled Multiplex Graph Representation Learning.\" ICML (2023).\n\nOnce again, we sincerely appreciate your time and effort in reviewing our paper. Your constructive criticism has been invaluable in refining our work, and we hope these adjustments and explanations can address your concerns satisfactorily.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their valuable and insightful comments. We are glad that the reviewers find that our studied problem is novel and significant. Here, we provide a PDF file to further address the reviewers’ concerns regarding the clarity of the paper and the completeness of the experiments.

**P1: The robustness analysis against feature noise. (To Reviewer cF8g)**

 Figure 5 in the PDF file shows the performance of InfoMGF and various baselines on the ACM dataset when injecting random feature noise. It can be observed that InfoMGF exhibits excellent robustness against feature noise, while the performance of SUBLIME degrades rapidly. As a single graph structure learning method, SUBLIME’s performance heavily relies on the quality of node features. In contrast, our method can directly optimize task-relevant information in multi-view graph structures (e.g., edges shared across multiple graphs are likely to be shared task-relevant information, which can be directly learned through $\mathcal{L}_s$), thereby reducing dependence on node features. Consequently, InfoMGF demonstrates superior robustness against feature noise.

**P2: The algorithmic process for InfoMGF-RA. (To Reviewer cF8g)**

Thank you for your question about the specific differences between InfoMGF-RA and InfoMGF-LA. In the PDF file, Algorithm 1 provides the algorithmic process for InfoMGF-RA. You can compare it with the algorithmic process for InfoMGF-LA in the Appendix of our original paper for a better understanding of their differences. Specifically, the total loss for both is the same, with the main difference lying in the graph structure augmentation methods. Additionally, InfoMGF-LA employs an alternating optimization strategy, which involves two optimization passes per epoch to optimize both the total loss and the augmented graph generator loss. In contrast, the optimization process for InfoMGF-RA is simpler, requiring only the optimization of the total loss.

**P3: Detailed explanations of frequently used notations. (To Reviewer 2Joh)**

Thank you for your suggestions regarding the notation definitions. To make the symbols used in the paper clearer and easier to understand, we have provided explanations in Table 4 of the PDF file under “Frequently used notations”. We will also include this table in the Appendix of the final version.

**P4: The scalability of InfoMGF. (To Reviewers ei6T and gjsJ)**

Thank you for your concerns about scalability. Here, we provide the overall complexity of our method. Let $V$, $N$, $m$, and $d_f$ represent the numbers of graphs, nodes, edges, and features. To simplify the overall complexity, we denote the larger terms within the layers of graph learner, graph encoder GCN, and non-linear projector as $L$, the larger terms between hidden-layer dimension and representation dimension as $\hat{d}$, the larger terms between batch sizes of locality-sensitive $k$NN and contrastive loss as $B$. The overall complexity of both InfoMGF-RA and InfoMGF-LA during the training process is $\mathcal{O}(VmL\hat{d}+VNL\hat{d}^2+VNd_f(\hat{d}+L)+VNB(d_f+V\hat{d}))$, which is comparable to mainstream unsupervised GSL models, including our baselines. For example, SUBLIME [1] needs to be trained on each graph in a multiplex graph dataset, and its time complexity is $\mathcal{O}(VmL\hat{d}+VNL\hat{d}^2+VNd_f(\hat{d}+L)+VNB(d_f+\hat{d}))$, which only has a slight difference in the last term compared to the time complexity of our method.

[1] Liu et al. "Towards Unsupervised Deep Graph Structure Learning." WWW (2022).

Meta-review: This paper introduces InfoMGF, a framework for unsupervised multiplex graph learning that refines graph structures to remove noise and maximize task-relevant information through mutual information maximization across different graph views. The method effectively addresses the issue of graph structure reliability and shows superior performance in clustering and classification tasks, even outperforming some supervised approaches. While initial concerns were raised about scalability and the clarity of differences between InfoMGF variants and other methods, the authors' rebuttal provided detailed explanations and additional experiments that addressed these concerns.
Decision: Accept (poster)