Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective
Authors: Yujie Mo
Zhihe Lu
Runpeng Yu
Xiaofeng Zhu
Xinchao Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Heterogeneous graph
Spectral clustering
Self-supervised learning
Primary area: graph_neural_networks
TL;DR: We theoretically revisited existing self-supervised heterogeneous graph learning from the spectral clustering perspective and introduced a novel framework to alleviate issues in existing works.

Abstract: Self-supervised heterogeneous graph learning (SHGL) has shown promising potential in diverse scenarios. However,  while existing SHGL methods share a similar essential with clustering approaches, they encounter two significant limitations: (i) noise in graph structures is often introduced during the message-passing process to weaken node representations, and (ii) cluster-level information may be inadequately captured and leveraged, diminishing the performance in downstream tasks. In this paper, we address these limitations by theoretically revisiting SHGL from the spectral clustering perspective and introducing a novel framework enhanced by rank and dual consistency constraints. Specifically, our framework incorporates a rank-constrained spectral clustering method that refines the affinity matrix to exclude noise effectively. Additionally, we integrate node-level and cluster-level consistency constraints that concurrently capture invariant and clustering information to facilitate learning in downstream tasks. We theoretically demonstrate that the learned representations are divided into distinct partitions based on the number of classes and exhibit enhanced generalization ability across tasks. Experimental results affirm the superiority of our method, showcasing remarkable improvements in several downstream tasks compared to existing methods.

Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective
Yujie Mo
Zhihe Lu
Runpeng Yu² Xiaofeng Zhu Xinchao Wang?*
School of Computer Science and Engineering, University Electronic Science and Technology of China National University of Singapore
Abstract
Self-supervised heterogeneous graph learning (SHGL) has shown promising poten- tial in diverse scenarios. However, while existing SHGL methods share similar essential with clustering approaches, they encounter two significant limitations: (i) noise in graph structures is often introduced during the cesssage-passingg process to weaken node representations, and (ii) cluster-level information may be inade- quately captured and leveraged, diminishing the performance in downstream tasks. In this paper, address these limitations by theoretically revisiting SHGL from the spectral clustering perspective and introducing a novel framework enhanced by rank and dual consistency constraints. Specifically, our framework incorporates a consttonst spectral clustering method that refines the affinity matrix to integrate node-level and cluster-level
exclude noise effectively. Additionally, consistency constraints that concurrently capture invariant and clustering informa- tion to facilitate learning in downstream tasks. We theoretically demonstrate that the learned representations are divided into distinct partitions based on the number of classes and exhibit enhanced generalization ability across tasks. Experimental results affimm the superiority of our method, showcasing remarkable improvements in several downstream tasks compared existing methods.
Introduction
Self- self-supervieed heterogeneous graph learning (SHGL) aims to effectively process diverse types of nodes and edges in the heterogeneous graph, producing low-dimensional representations without the need for human annotations [72, 71, 25). Thanks to its remarkable capabilities, SHGL. has attracted significant interest and has been utilized in broad array of applications, including recommendation systems [44, 12], social network analysis [45, 9], and molecule design [68, 59].
Existing SHGL methods can be broadly classified into two groups, i.e., meta-path- veta--ath-bbsed based methods and seattive-grap--baseee methods. Meta-path- based methods typically utilize pre-defined meta-paths to explore relationships among nodes that may share the same label in the heterogeneous graph [18, 74]. However, building meta- meta-paths requires extensive prior knowledge and incurs additional computation costs [69]. To address these drawbacks, adaptive-graph crre--rrphhbbeeae baseh methods dynamically assign significant weights to node pairs likely to share the same lahel, using the adaptive graph structure rather than traditional meta-paths [30]. Both groups of SHGL methods facilitate within the same class, either through meta-path-base graphs or adaptive graph structures. As a result, this process minimizes intra-class differences and promotes clustered pattern in the learned representations, aligning these methods closely with conventional clustering techniques.
among nodes
"Corresponding authors
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

H
Projection
Oxhoogonal Layer
head P
A Argmax
13
Orthogomal Layer
Multi-lay
Perceptron g
DKx
Matmul X
dk
Z
Projection
Cluster Pooling
Hetorugemeeus
head 4
Excoder f
101
Projection
head
Figure 1: The flowchart of SCHOOL, which first employs the Multi-Layer Perception I6 to derive semantic representations H. followed by obtaining orthogonal cluster assignment matrix Y and orthogonal H. Subsequently, SCHOOL filters noisy connections by deriving the rank-constrained affinity matrix S. which further used to multiply with H and then obtaín node representations Z. Meanwhile, SCHOOL a heterogeneous encoder So to aggregate information across node types, yielding heterogeneous representations Z. Finally, SCHOOL incorporates spectral loss L.p to optimize Y to fit eigenvectors of the Laplacian matrix S. Moreover, SCHOOL designs node-level (i.e., Lic) and cluster-level (i.e., Loo) consistency constraints projected representations (i.e., Q and Q) and cluster representations Q capture the invariant and clustering information, respectively.
Despite the effectiveness of previous SHGL methods, they encounter limitations. First, previous methods conduct message- -arggggggggingggggg relying on meta- vetta-path-base graphs and adaptive graph structures, which inevitably include noise, i.e., connections among nodes from different classes [18. 58]. Conse- quently, such noise compromises the identifiability of node representations after the message-pass pagseggggnnngggg. process. Second, while previous methods exhibit clustering characteristics, they typically emphasize the node-level consistency only, neglecting to capture and leverage the cluster-level information effectively [57, 30]. This may not fully exploit the potential benefits of clustering for representation learning, thereby diminishing the performance of downstream tasks.
Based on the above analysis, it is feasible analyze previous SHGL methods from clustering perspective thanks to their close connection to clustering techniques and further optimize the graph structures to mitigate noisy connections as well as harness the cluster-level information enhance previous SHGL. To achieve this, there are three key challenges, i.e., (i) How to formally understand previous SHGL methods from the clustering perspective? (ii) With insights from the clustering analysis, how to learn an adaptive graph structure that effectively captures intra-class connections while filtering out inter-class noise? (iii) How to enable the effective incorporation of cluster-level information in the heterogeneous graph to boost the performance of downstream tasks?
In this paper, we address the outlined challenges by first theoretically revisiting previous SHGL methods from a clustering perspective and then introducing novel framework, termed Spectral Clustering-inspired HeterOgeneeUs graph Learning (SCHOOL for short), that incorporates rank- constrained spectral clustering and dual consistency constraints, as depicted in Figure 1. Specifically, we start by proving that existing SHGL can be reformulated as spectral clustering with an additional regularization term under the assumption of orthogonality, thus addressing challenge (i) and laying the foundational theory for our approach. Next, tackle challenge (ii), we propose an efficient spectral clustering technique that includes rank constraint on the affinity matrix, aiming to effectively mitigate noisy connections among different classes. Furthermore, to resolve challenge (iii), we design dual consistency constraints at both node and cluster levels to capture invariant and clustering information, respectively, which reduces the intra-cluster differences and enhances the performance of downstream tasks. Finally, theoretical analysis indicates that the learned representations are divided into distinct partitions corresponding to the number of classes, and are demonstrated superior generalization ability compared to those derived from previous SHGL methods.

---

Compared to previous SHGL works, our contributions can be summarized as follows:
To the best of our knowledge, we make the first attempt to theoretically revisit previous SHGL methods from the spectral clustering perspective in unified manner.
We adaptively learn rank-constraained affinity matrix to mitigate noisy connections inherent in previous SHGL methods. Moreover, we introduce dual consistency constraints to capture both invariant and clustering information enhance the effectiveness of our method.
We theoretically demonstrate that the proposed method divides the learned representations into distinct partitions based on the number of classes, instead of dimensions in previous SHGL methods. Furthermore, the representations obtained by this method exhibit enhanced generalization ability compared to those derived from previous SHGL methods.
We experimentally manifest the effectiveness of the proposed method across a variety of downstream tasks, using both heterogeneous and homogeneous graph datasets, compared to numerous state-of-the-art methods.
2 Method
represent a heterogeneous graph, where V and & indicate set of nodes and set of edges, respectively. X {x: | denotes the matrix of node features, where indicates the number of nodes. Moreover, T and R indicate set of node types and set of edge types, respectively. Given the heterogeneous graph G, most existing SHGL methods utilize meta-paths or adaptive graph structures to explore connections among nodes within the same class, thus exhibiting the characteristics of clustering and obtaining discriminative representations. To gain a deeper insight of previous SHGL methods, we first propose to revisit them from a clustering perspective as follows.
Notations. Let G = (V,,,
2.1 Revisiting Previous SHGL Methods from Spectral Clustering
As mentioned above, previous SHGL methods tend to conduct clustering implicitly, relying on meta-path-based graphs adaptive graph structures. For example, given academic heterogeneous graph with several node types (Lee, paper, author, and subject), for the meta- patt--pth---aa patt--ptthheeeeee based methods, two papers belong the same class, there may exist meta- meta-path path "paper-subject subbject-paper" to connect them (i.e., two papers are grouped into the same subject). Similarly, for the adaptive-gres saaeee-grap--baae based methods, when two papers belong to the same class, the adaptive graph structures likely assign large weights to connect them. Therefore, representations of nodes within the same class will be close to each other after the message-passinng process, thus implicitly presenting clustered pattern.
Based on the above observation, actually. we can further theoretically understand previous SHGL methods from the clustering perspective. To do this, we first give the following definition.
Definition 2.1. (Spectral Clustering) Given the Laplacian matrix L, the optimization problem of the spectral clustering can be described as follows:
min Tr LH S.L., H-H=I, H
where D W, W E Raxn a data similarity matrix, D a diagonal matrix whose entries column sums of W. H Raxd is representations matrix, Tr(-) indicates the matrix trace, and I indicates the identity matrix.
According Definition 2.1, for both meta-path-based methods [31, 57, 58] and Slaptive-graph-baase SHGL methods [30], we then have Theorem 2.2, whose proof can be found in Appendix C.I.
Theorem 2.2. Assume the learned representations H are orthogonal, optimizing previous meta-path- based and adaptiie-graplee graph-based SHGL methods is equivalent performing spectral clustering with additional regularization, i.e.,
min LSHEL = min Tr(""LLH + R(H) S.L, H'H
where R(-)) indicates the regularization term, L indicates the Laplacian matrix of the meta meta-path-burt based graph the adaptive graph structure.
3

---

Theorem 2.2 reveals the connection between previous SHGL and the spectral clustering as well as indicates that previous SHGL heavily relies on the Laplacian matrix of meta-path- petta-pat-bbsedd bauth graph or adaptive graph structure. Moreover, based on Theorem 2.2, we can further bridge previous SHGL and the graph-cut algorithm [54] as follows, whose proof can be found in Appendix C.2.
Theorem 2.3. Under the same assumption in Theorem 2.2, optimizing previous meta- nelaa-ath-based and adaptive grapg--appuheee based SHGL methods is approximate to performing the RatioCut (V1...., Va) algorithm that divides the learned representations into d partitions {V1...., Va). i.e.
min LSNGL = min RatioCut (V1,..., Va), H
where d indicates the dimension of representations' H.
Theorem 2.3 further indicates that previous SHGL methods divide the learned representations into d partitions, where d is generally much larger than the number of classes. Therefore, Theorem 2.3 connects the traditional graph-cut algorithm with existing SHGL methods, which requires custom analysis. As a result, we theoretically revisit previous SHGL methods from spectral clustering as well as graph-cut perspectives and build the connections between them, thus solving the challenge (i).
2.2 Rank-Constrained Spectral Clustering
Based on the connections between previous SHGL methods and the spectral clustering as well as the graph-cut algorithm, we have the observations as follows. First, according to Theorem 2.2, previous SHGL methods conduct spectral clustering based on the Laplacian matrix of meta-path-based graph or adaptive graph structure, which may not guarantee optimality and could potentially contain noisy connections, thus affecting the spectral clustering. Second, according to Theorem 2.3, previous SHGL methods conduct the graph-cut to divide the learned representations into d partitions, which are generally not equal to the number of classes c. As a result, optimizing previous SHGL methods becomes hard even error problem, and the learned representations can not be clustered well. Therefore, it is intuitive to mitigate noise in the adaptive graph structure as well as divide the learned representations into exactly partitions to improve existing SHGL methods.
Specifically, in this paper, we propose to learn an adaptive affinity matrix with the rank constraint to mitigate noisy connections as much as possible. To do this, we first employ the Multi-Layer Perceptron (MLP) as the encoder JΦ E R. (xi to obtain the semantic representations by:
H (X),,,),
where f and d1 are the dimensions of node features and representations, respectively, and a is the activation function. After that, we propose to learn an adaptive affinity matrix S E Rax based on the semantic representations. Intuitively, in a uncorrelated representations subspace, a smaller distance [h; hyll between semantic representations should be assigned a larger probability Sij. Therefore, it is a natural approach to learn the affinity matrix S by:
ming Σi,= b h, 121 + as?;) s.t. 1,0 S s; 1.
where a non- non-negative parameter. In Eq. (5), the first term encourages the affinity matrix assign large weights to node pairs with small distances. Moreover, the second term avoids the trivial solution that only the nearest node can be the neighbor of i; with probability However, similar to previous SHGL methods, usually the affinity matrix learned by Eq. (5) can not reach the ideal case (i.e. having no noisy connections among different classes and containing exactly c connected components). As result, the noisy connections in the affinity matrix may induce negative interference during the message-passing process. To solve this issue, we first introduce the following lemma in [32].
Lemma 2.4. The multiplicity of the eigenvalue 0 of the Laplacian matrix Lg is equal to the number of connected components in the affinity matrix S.
Lemma 2.4 indicates that if the rank of Ls equals to n c, then the affinity matrix S contains exactly connected components to achieve the ideal scenario, where Lg D
S+s"" -== and D is the degree matrix of S+s". Based on Lemma 2.4, we can solve the above issue by adding the rank constraint on the affinity matrix, i.e., enforcing the smallest c eigenvalues of Lg to be 0:
rank(Ls) = n - c > min
To (Ls),
(6)

---

where (Ls) is the i-th smallest eigenvalue of Lg and (L()s) 2 0 because Lg is positive semi- definite. Moreover, according Ky Fan's Theorem [5], the constraint in Eq. (6) can be rewritten in the spectral clustering form as follows (derivation listed in Appendix C.5).
Ta (Ls) min Tr(F FFF-
L)))=
min F P'F-12
Sty Σ 1
|I. f
(7)
where F E R is formed by part eigenvectors of Ls after the eigendecomposition. Therefore, based on Eq. (7), we can add the rank constraint on the affinity matrix and reformulate Eq. (5) as:
mins.F F Ex (llb - E + as + 3 311.. - =,)
(8)
S.L., Vi, 1,0 < s, S 11,F=F=1
where 3 is non-negative parameter. Eq. (8) can be solved by applying the alternating optimization approach. Specifically, when is fixed, Eq. (8) becomes minprF-1 -in= |[f; - fy 112 8, = 2 minprr-1 Lr(F"LgF), whose optimal solution F is the eigenvectors of Lg corresponding to the smallest eigenvalues. When F is fixed, denote d, ||h, h written in the vector form, i.e.,
2 + 3 fg122 Eq. (8) can be
min 1=
||s + d.
(9)
2a
According to the Lagrangian function of Eq. (9) and the KKT condition [3], we can obtain the closed-form solution of the element Sij in the affinity matrix, i.e.
1
Sty = 2 di + A)+
(10)
2a
where À is a non-negative parameter. and (.)+ indicates max 0}. In practice, sparse affinity matrix usually obtains better performance and reduces computation costs. Therefore, we only calculate 8.j between node and its k nearest neighbors. Then parameters a and À can be further determined, details listed in Appendix C.6.
However, when fixing S and optimizing F in Eq. (8), computation costs of obtaining eigenvectors remain prohibitive due the cubic time complexity of the eigendecomposition. To address this issue, we propose to replace the eigendecomposition with a projection head and orthogonal layer [42]. Specifically, we first employ the projection head P.p e gd to map semantic representations to the cluster assignment space P e R i.e.,
P P= (pp HH)),
(11)
where is the activation function. After that, we employ orthogonal layer derive the orthogonal cluster assignment matrix Y E Raxe (orthogonal derivation listed in Appendix C.7), i.e.
Y= VnP 1R-1),
(12)
where R is an upper triangular matrix obtained from the QR decomposition [6] (i.e., P = ER and E I) the full rank P. Similarly, we can also implement the orthogonal layer to achieve the uncorrelation (i.e., H = D) on the representations subspace.
As result, the projection head and the orthogonal layer act linear transformation to achieve the orthogonality constraint on Y. To replace the cigendecomposition. the cluster assignment matrix Y should further fit the eigenvectors F in Eq. (8). To do this, design spectral loss Lep to optimize the parameters in Pe to simulate the spectral clustering of the third term in Eq. (8), ie.,
Lap
n2 Eij-1 Sig Ily: y, HH(Y)
(13)
where 7 is a non-negative parameter, H(Y) = P(y")(o assignment probabilities P(y') = + iY), and y indicates the i-th column and j-th row of y. According to Eq. (7), the first term Eq. (13) simulates the spectral clustering to enforce the learned cluster assignment matrix Y to approximate eigenvectors F, and the second term is a widely used regularization term [1, 14] to avoid the trivial solution that most nodes are assigned to the same cluster. Therefore, when S is fixed, we optimizing Y to approach the optimal F by achieving orthogonality
is the entropy of cluster
5

---

with Eq. (12), and fitting eigenvectors F with Eq. (13). As result, this reduces the cubic time complexity of eigendecompostiion to Ond + ne² nkd nke c dd), where d?, c² n, thus is linear to the sample size, details are shown in Appendix B.2. Finally, the proposed method still optimizes the affinity matrix and eigenvectors F Eq. (8) in an alternating approach, i.e., fix F and then obtain the closed-form solution of S, and fix S and then optimize parameters (ie., Is and Pp) to update Y to approach the optimal F.
Therefore, the proposed method obtains the affinity matrix with exactly с connected components to mitigate noisy connections in an effective and efficient way. Then we can obtain the node representations Z = SH, which is expected to conduct message- -aassing among nodes within the same class. Moreover, we can bridge the connections between the proposed method and the spectral clustering as well as the graph-cut algorithm as follows, whose proof can be found in Appendix C.3.
Theorem 2.5. Optimizing the spectral loss Lep leads to performing the spectral clustering based on the affinity matrix S with e. connected components and conducting RatioCut (V1...., ........e). algorithm to divide the learned representations into e partitions, i.e.,
min Cep + min Ls(Y"LsS)) + min RatioCut(V Vo).
(14)
Theorem 2.5 indicates that the proposed method conducts the spectral clustering as previous SHGL methods, but is performed Section 3.2.3), thus mitigating noisy connections from different classes and solving the challenge (ii). Moreover, the proposed method divides the learned representations into partitions, which is better optimization goal than previous SHGL methods to obtain discriminative representations.
affinity matrix with exactly connected components (verified in
2.3 Dual Consistency Constraints
The message-passingg among nodes within the same class reduces intra-class differences and enhances node representations Z. Meanwhile, the message-passing among nodes from different types also contributes to obtaining task-related contents and benefits downstream tasks [69]. To do this, we propose aggregate the information of nodes from different types in the heterogeneous graph with heterogeneous encoder fo E /xd:
Specifically, for the node U4 concatenate the information of itself and its relevant one-hop neighbors (i.e., nodes of other types) based on edge types in R. and then derive the heterogencous representations Ž by:
2,
Σ ofo(x)))l FER
Σ fa(x,)), MEN,,
(15)
R
where a is the activation function, [R] indicates the number of edge types, Mi., indicates the set of one-hop neighbors of node U; based on the edge type r E R, fo(-) indicates the linear transformation, and .|I indicates the concatenation operation. Therefore, the heterogeneous representations Ž aggregate the information of nodes from different types to introduce more task-related contents.
Given node representations Z and heterogeneous representations Ż, most previous SHGL methods utilize the node-level consistency constraint (e.g., Info-NCE loss [36]) to capture the invariant information between them and enhance the effectiveness [57, 30]. In addition, according to Theorem 2.2, previous SHGL methods actually perform spectral clustering to learn node representations. However, previous SHGL methods fail utilize the cluster-level information outputted by the spectral clustering, thus weakening the downstream task performance. To solve this issue, we design dual consistency constraints to capture the invariant information well the clustering information between Z and Z.
Specifically, we first employ a projection head dy TR xd2 to map both and Ż into the same latent space, i.e., Q 44 (Z) and Q = 9, (Z), where d2 the projected dimension. Then we follow previous works [57, 58) to design a node-level consistency constraint capture the invariant information between and Q i.e.
Lnc |Q
Q1 + log -i ccu
(16)

---

where C - -'Q-Q"Q, and is non-negative parameter. Similar to previous works, the first term in Eq. (16) enforces representations in Q agree with the corresponding representations in Q, thus capturing the invariant information between them. The second term enables different dimensions of Q and Q to uniformly distribute over the latent space to avoid collapse.
In addition to the node-level consistency constraint, we further design the cluster-level consistency constraint to capture the clustering information from the cluster assignment matrix Y. To do this, first obtain the cluster indicator matrix Y based on the cluster assignment matrix Y, i.e., Y argmax(Y)) After that, we conduct average pooling on node representations that possess the same cluster indicator to obtain the j-th cluster representation مÿ. i...
Σ
m,,,, qi
(17)
where Vj indicates the set of nodes whose cluster indicators equal to j. and [Vgl indicates the number of nodes in Vz- Then design cluster-level consistency constraint cluster representations Q and projected representations to capture the clustering information, i.e.,
Lee Σ |qq: dy.
(18)
where qy, indicates the cluster representation whose label equals to y,. Eq. (18) enables the projected representation qi and the cluster representation qy, to align each other. As result, representations capture the clustering information based cluster indicators and reduce intra-cluster differences to improve the performance of downstream tasks, thus solving challenge (iii).
We integrate the spectral loss in Eq. (13), the node-level consistency constraint in Eq. (16), with the cluster-level consistency constraint in Eq. (18) to have the objective function as:
J Ssp + pLac + 8L
(19)
where l and are non-negative parameters. Finally, concatenate node representations Z with heterogeneous representations Z obtain representations for downstream tasks. Actually, for the learned representations, we have the following Theorem, whose proof can be found in Appendix C.4.
Theorem 2.6. The proposed method with dual consistency constraints achieves a lower boundary of the model complexity C and higher generalization ability boundary G than previous SHGL with the node-level consistency constraint only, i.e..
(CsCHHoL)) < iCH(CH)))), sup(GscHooL) > sup(GsHcL),
(20)
where inf(.) and sup(-) indicates lower bound and upper bound, respectively.
Theorem 2.6 indicates that the representations learned by the dual consistency constraints can be theoretically proved to exhibit superior generalization ability than the representations learned by previous SHGL methods with the node-level consistency constraint only, thus expected to perform better in different downstream tasks (verified in Section 3.2).
Experiments
In this section, we conduct experiments on both heterogeneous and homogeneous graph datasets to evaluate the proposed method in terms of different downstream tasks (i.e., node classification and node clustering), compared both heterogeneous and homogeneous graph methods. Detailed settings are shown in Appendix D, and additional results are shown in Appendix E.
3.1
Experimental Setup
3.1.1 Datasets
The used datasets include four heterogeneous graph datasets and two homogeneous graph datasets.
Heterogeneous graph datasets include three academic datasets (i.e., ACM [56], DBLP [56], and Aminer [1]]), and one business dataset (i.e., Yelp [27]). Homogeneous graph datasets include two sale datasets (i.e., Photo and Computers [43]).
7

---

Table 1: Classification performance (i.e.,
Macro-F1 and Micro-F1) on heterogeneous graph datasets.
ACM
Yelp
DBLP
Aminer
Method
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
DeepWalk
73.9++0.3
74.1+0.1
68.7+11.1
73.2+009
88.1
09.
54.7+0.8
59.7+40.7
GCN
86,9=002
87.0+0.3
85.010.6
87.410.8
90.2+0.2
90.9
64.510.7
71.52009
GAT
85.0=10.4
84.911..3
86.410..
88.210.7
91.010.4
92.1=0.2
63.820.4
70.620..7
Mp2vec
87.6+0.5
88.1+0.3
78.2+0088
83.6+-0.9
85.7+0.3
87.6+00.6
58.7+-0.5
65.3+0.6
HAN
89.4+00.2
89.2+0.2
9..5+1.2
90.7+
91.2++0.4
92.0=00.5
65.3+0077
72.8+0.4
HGT
91.5.10.7
91.6110.6
89.910.5
90.2110.6
90.910.6
91.7.1088
64.510.5
71.010.7
DMGI
89.810.11
89.810.11
82.910.8
85.810.9
92.110.2
92.910.33
63.810.4
67.610.5
DMGlattn
88.710..3
88.7.0..5
82.810.7
85,410.55
90.910.2
91.810.33
62.410.9
66.810.8
HDMI
00.1
90.1+
80.7#0.6
84.0#00.9
91.3=002
92.2=0.55
65,9#044
71.7=006
HeCo
88.3+0.3
88.2+0.2
85.3+0.7
87.9+0.6
91.0+
91.6=0.2
71.8=0.9
78.6+0.7
HGCML
90.6=00.7
90.7#0.5
90.7+0.8
91.0:10.7
91.9
93.2=0.7
70.5+0.4
76,3+0.6
CPIM
91.4+10.3
91.3++0.2
90.2410.5
90.3110.4
93.2
93.8-088
70.1
15.8
HGMAE
90.5++0.5
90.64-0.7
90.5+00.7
90.7+00.5
92.9+0.5
93.4+0.6
72.3+0.9
80.3
HERO
92.2+-0.5
92.1+0077
92.4+0.7
92.3+0066
93.8+0.66
94.440.4
75.1+0.7
84.5+0.9
SCHOOL
92.7=0.6
92.610.55
93.011..7
92,810.4
94.020.3
94.710.4
77.510.9
86.810..7
3.1.2
Comparison Methods
The comparison methods include eleven heterogeneous graph methods and twelve homogeneous
graph methods. The former includes two semi-supervised methods (i.e. HAN [56] and HGT [13]).
one traditional unsupervised method (i.e., Mp2vec [4]), and eight self-supervised methods (i.e., DMGI [38], DMGlattn [38], HDMI [18], HeCo [57], HGCML [58]. CPIM [31], HGMAE [48], and HERO [30). The latter includes two supervise methods (i.e., GCN [20] and GAT [50]), one traditional unsupervised method (i.e., WeepWalk [41]), and nine self-supervised methods, (i.e., DGI [51], GMI [40], MVGRL [8], GRACE [75], GCA [76), G-BT [2], COSTA [70], DSSL, [61], and LRD [63]).
For fair comparison, we follow [4, 56, 27, 28] to select meta-paths for previous meta-path- based SHGL methods. Moreover, we follow [29] implement homogeneous graph methods on heteroge- neous graph datasets by separately learning the representations of each meta-path- graph and further concatenating them for downstream tasks, In addition, we replace the heterogeneous encoder fe with GCN to implement the proposed method on homogeneous graph datasets because there is only one node type the homogeneous graph. Moreover, we follow previous works [76] generate two different views for the homogeneous graph by removing edges and masking features. The code of the proposed method is released at https:/ //gi thub. com Yujj MeMo /SHHOLL.
3.2 Results Analysis
3.2.1 Effectiveness on Heterogeneous and Homogeneous Graph
We first evaluate the effectiveness of the proposed method on the heterogeneous graph datasets and report the results of node classification and node clustering in Table 1 and Appendix E, respectively. Obviously, the proposed method obtains better performance on both node classification and node clustering tasks than comparison methods.
Specifically, first, for the node classification task, the proposed method consistently outperforms the comparison methods by large margins. For example, the proposed method on average, improves by 1.1%, compared to the best SHGL method (i.e.. HERO). on four heterogeneous graph datasets. The reason can be attributed to the fact that the proposed method adaptively learns rank-constrained affinity matrix to mitigate noisy connections among different classes, thus reducing intra-class differences. Second, for the node clustering task, the proposed method also obtains promising improvements. For example. the proposed method on average, improves by 3.1 3.1%, compared to the best SHGL method (i.e., HGMAE), on four heterogeneous graph datasets. This demonstrates the superiority of the proposed method, which simulates the spectral clustering with the spectral loss and conducts the cluster-level consistency constraint to further utilize the clustering information. As result, the effectiivnees of the proposed method is verified on different downstream tasks.
8

---

Table 2: Classification performance (i.e., Macro-F1 and Micro-F1) of each component in the objective function I on all heterogeneous graph datasets.
ACM
Yelp
DBLP
Aminer
Cup Line Lee
Macro-F
Micro-F1
Macro-Fl
Micro-F1
Macro-F1
Micro-FI
Macro-F1
Micro-Fi Fl
8..9
85.8:10.6
91.8:10.6
91.3:10.55
91.0.:..2
92.1+0.4
66.8:10.7
75.5
V
88.8++0.6
88.6+10.7
92.5+0.7
92.1+0.4
91.7++044
92.7+0.5
72.4+00.5
80.3+00.7
87.6=0.33
87.510.55
92.310.8
92.0=0.6
90.710.6
91.740.6
67.3:10.6
74.7=0.5
V
86.910..7
86.710.5
92.110.3
91.510.4
93,410.8
94.2:10.6
75.21004
83.910.7
89.0=10.5
88.910.4
92.410.5
92.010.3
93.510.6
94.210.4
76.2:0..5
85.210.8
V
88.9+0.7
88.8+00.6
92.6+0.6
92.3+0.5
91.9+0.7
92.8+0.8
77.1+0.8
86.0+0.6
V 92.7++0.6
92.6+-0.5
93.0++0.7
92.8+0.4
94.0+0.3
94.7+0044
77.5+009
8..8+0.7
We further evaluate the effectiveness of the proposed method on homogeneous graph datasets and report the results of node classification in Appendix E. We can observe that the proposed method also achieves competitive results on the homogeneous graph datasets compared to other homogeneous graph methods. For example, the proposed method outperforms the best self-supervised method (i.e. LRD), on almost all homogeneous graph datasets. This indicates that the proposed method also available learn the noise-free affinity matrix for homogeneous graphs as well as capture invariant and clustering information to benefit downstream tasks. Therefore, the effectiveness of the proposed method verified on both heterogeneous and homogeneous graph datasets.
3.2.2 A Ablation Study
The proposed method investigates the objective function I to learn the rank- constrindd affinity matrix, as well as capture invariant and clustering information. To verify the effectiveness of each component of J (i.e., Lep, Lue, and Lec), we investigate the performance of all variants on the node classification task and report the results in Table 2.
From Table 2, we have the observations as follows. First, the proposed method with the complete objective function obtains the best performance. For example, the proposed method average improves by 1.8%, compared to the best variant (i.e., without Cnc). indicating that all components in the objective function are necessary for the proposed method. This is consistent with our claims, i.e. it is essential to optimize the adaptive graph structure to mitigate noisy connections as well as utilize the cluster-level information to benefit downstream tasks. Second, the variant without L.p achieves inferior results to the other two variants (i.e., without Lne and without Lee, respectively). This can be attributed the fact that the spectral loss Cap enforces the cluster assignment matrix to fit the eigenvectors, which is necessary for the closed-form solution of the affinity matrix.
3.2.3 Visualization
To verify the effectiveness of the learned affinity matrix and the representations for downstream tasks, we visualize the affinity matrix in the heatmap and visualize the representations with t-SNE [49] on DBLP and Aminer datasets and report the results in Figure 2.
Specifically, we randomly sample 50 nodes each class and then visualize elements of the affinity matrix S among sampled nodes with the heatmap, where rows and columns are reordered by node labels. In the correlation map, the darker a pixel, the larger the value of the element of S. In Figures 2(a) and 2(c), the heatmaps exhibit that there are nearly (i.e., the number of classes) components in the affinity matrix, and almost all elements with large values fall in the block diagonal structure. This indicates that the affinity matrix indeed contains connected components mitigate noisy connections among different classes. Moreover, the t-SNE visualization in Figures 2(b) and 2(d) further indicate that the learned representations can be well divided into e partitions. This is consistent with the observation in Theorem 2.5 and verifies the effectiveness of the learned representations.
4 Conclusion
In this paper, we revisited previous SHGL methods from the perspective of spectral clustering and then introduced novel framework to alleviate existing issues. Specifically, we first proved that optimizing

---

(a) S of DBLP
(b) 1-SNE of DBLP
(c) S of Aminer
(d) t-SNE of Aminer
Figure 2: Visualization of the affinity matrix S and t-SNE on DBLP and Aminer datasets.
previous SHGL methods equivalent to performing spectral clustering with additional regularization under the orthogonalization assumption. Then we proposed an efficient spectral clustering method with the rank constraint to learn an adaptive affinity matrix and mitigate noisy connections in previous methods. Morcover, we designed node-level and cluster-leve consistency constraints to capture invariant and clustering information, thus benefiting the performance of downstream tasks. Theoretical analysis indicates that the learned representations are divided into distinct partitions based on the number classes, and are expected to achieve better generalization ability than representations of previous SHGL methods. Comprehensive experiments verify the effectiveness of the proposed method on both homogeneous and heterogeneous graph datasets on different downstream tasks.
Potential limitations and broader impact. Our potential limitation is that this work is designed based on node features. However, in heterogeneous graphs, instances arise where nodes are devoid of features. While one-hot vectors structural embeddings be designated node features to tackle this problem, we recognize the necessity of devising dedicated techniques tailored for hetcrogeneous graphs with missing node features. In addition, the proposed method can also be used to deal with the homophily problem, which aims to explore the connections within the same class. We consider these aspects potential directions for future research. Despite the great development of SHGL, some theoretical foundations are still lacking. Our work theoretically connects existing SHGL methods and path understanding and designing SHGL. Besides that,
spectral clustering and may open do not foresee any direct negative impacts on the society.
Acknowledgments
This project is supported by the National Key Research and Development Program of China under Grant No. 2022YFA 1004100, the Natural Science Foundation of Guangdong Province of China under Grant No. 2024A151501 1381, and the National Research Foundation, Singapore, under its AI Singapore Programme (AISG Award No: AISG2-RP-2021-022
References
[1] Liang Bai and Jiye Liang. Sparse subspace clustering with entropy-norm. In ICML, pages 561-568, 2020.
[2] Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V. Chawla. Graph barlow twins: A self-supervised representation learning framework for graphs. Knowledge- Systems, 256:109631, 2022.
[3] S Boyd, L Vandenberghe, and L Faybusovich. Convex optimization. IEEE Transactions on 2006.
Automutic Control, (1:1)): (1(1))1859-1880 159-1859,
[4] Yuxiao Dong, Nitesh V. Chawla, and Ananthram Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In SIGKDD, pages 135-144, 2017.
[5] Ky Fan. On a theorem of weyl concerning eigenvalues of linear transformations i. Proceedings of the National Academy Sciences, 35(1 (5511))652-655 1949.
[6] Walter Gander. Algorithms for the qr decomposition. Res. Rep, 80(02): 1980.
[7] Jeff 7. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. In NeurIPS, pages 5000-5011, 2021.
10

---

[8] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In ICML, pages 4116-4126, 2020.
[9] Dongxiao He, Chundong Liang, Cuiying Huo, Zhiyong Feng, Di Jin, Liang Yang, and Weixiong Zhang. Analyzing heterogeneous networks with missing attributes by unsupervised contrastive learning. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[10] Dongxiao He, Jitao Zhao, Rui Guo, Zhiyong Feng, Di Jin, Yuxiao Huang, Zhen Wang, and Weixiong Zhang. Contrastive learning meets homophily: two birds with one stone. In ICMI,, pages 12775-12789, 2023.
[11] Binbin Hu, Yuan Fang, and Chuan Shi. Adversarial learning heterogeneous information networks. In SIGKDD, pages 120-129. 2019.
[12] Binbin Hu, Chuan Shi, Wayne Xin Zhao, and Philip $ Yu. Leveraging meta-path based context for top-n recommendation with a neural co-attention model. In SIGKDD, pages 1531-1540, 2018.
[13] Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In WWW, pages 2704-2710, 20, 2020.
[14] Jiabo Huang, Shaogang Gong, and Xiatian Zhu. Deep semantic clustering by partition confi- dence maximisation. In CVPR, pages 8849-8858, 2020.
[15] Yudi Huang, Yujie Mo, Yujing Liu, Ci Nie, Guoqiu Wen, and Xiaofeng Zhu. Multiplex graph representation learning via bi-level optimization. In IJCAI, 2024.
[16] Yiding Jiang, Parth Natekar, Manik Sharma, Sumukh K Aithal, Dhruva Kashyap, Natarajan Subramanyam, Carlos Lassance, Daniel M Roy, Gintare Karolina Dziugaite, Suriya Gunasekar, al. Methods and analysis of the first competition predicting generalization of deep learning. In NeurlPS, pages 170-190, 2021.
[17] Di Jin, Luzhi Wang, Yizhen Zheng, Guojie Song, Fei Jiang, Xiang Li, Wei Lin, and Shirui Pan. Dual intent enhanced graph neural network for session-based new item recommendation. In Www, pages 684-693, 2023.
[18] Baoyu Jing, Chanyoung Park, and Hanghang Tong. Hdmi: High-order deep multiplex infomax. In WWW, pages 24 2414-2424, 2021.
[19] P. Diederik Kingma and Lei Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[20] N. Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In /CLR, pages 1-14, 2017.
[21] Marc T Law, Raquel Urtasun, and Richard S Zemel. Deep spectral clustering learning. In ICML, pages 1985-1994, 2017.
[22] Ke Liang, Lingyuan Meng, Meng Liu, Yue Liu, Wenxuan Tu, Siwei Wang, Sihang Zhou, Xinwang Liu, and Fuchun Sun. A survey of knowledge graph reasoning on graph types: Static, dynamic, and multimodal. arXiv preprini arXiv:2212.05770 2022.
[23] Meng Liu, Ke Liang. Yawei Zhao, Wenxuan Tu, Sihang Zhou, Xinbiao Gan, Xinwang Liu, and Kunlun He. superviid temporal graph learning with temporal and structural intensity alignment. IEEE Transactions on Neural Networks and Learning Systems, 2024.
[24] Meng Liu, Yue Liu, Ke Liang, Wenxuan Tu, Siwei Wang, Sihang Zhou, and Xinwang Liu. Deep temporal graph clustering. ICLR, 2024.
[25] Nian Liu, Xiao Wang, Deyu Bo, Chuan Shi, and Jian Pei. Revisiting graph contrastive learning from the perspective of graph spectrum. In NeurlPS, volume 35, pages 2972-2983, 2022.
[26] Yue Liu, Ke Liang, Jun Xia, Sihang Zhou, Xihong Yang, Xinwang Liu, and Stan Z. Li. Dink-net: Neural clustering on large graphs. In ICML, 2023.
[27] Yuanfu Lu, Chuan Shi, Linmei Hu, and Zhiyuan Liu. Relation structure heterogeneous information network embedding. In AAAI, pages 4456 4463, 2019.
[28] Qingsong Lv, Ming Ding, Qiang Liu, Yuxiang Chen, Wenzheng Feng, Siming He, Chang Zhou, Jianguo Jiang, Yuxiao Dong, and Jie Tang. Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks. In SIGKDD, pages 1150-1160, 2021.
11

---

[29]
Yujie Mo, Yajie Lei, Jialie Shen, Xiaoshuang Shi, Heng Tao Shen, and Xiaofeng Zhu. Disentan- gled multiplex graph representation learning. In ICML, pages 24983-25003 2023.
[30] Yujie Mo, Feiping Nie, Zheng Zhang, Ping Hu, Heng Tao Shen, Xinchao Wang, and Xiaofeng Zhu. Self-supervised heterogeneous graph learning: a homophily and heterogeneity view. In ICLR, 2024.
[31] Yujie Mo, Zongqian Wu, Yuhuan Chen, Xiaoshuang Shi, Heng Tao Shen, and Xiaofeng Zhu. Multiplex graph representation learning via common and private information mining. In AAAI, pages 9217-9225, 2023.
[32] Bojan Mobar, Y Alavi, G Chartrand, and OR Oellermann. The laplacian spectrum of graphs. Graph theory, combinatorics, and applications, 2(871 (1871-89)):2. 1991.
[33] Parth Natekar and Manik Sharma. Representation based complexity measures for predicting generalization in deep learning. arXiv preprint arXiv:20/2.02775. 2020.
[34] Feiping Nie, Xiaoqian Wang, and Heng Huang. Clustering and projected clustering with adaptive neighbors. In SIGKDD, pages 977-986, 2014.
[35] Feiping Nie, Danyang Wu, Rong Wang, and Xuelong Li. Self-weighted clustering with adaptive neighbors. IEEE Transactions on Neural Networks and Learning Systems, pages 3428-3441, 2020.
[36] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint arXhv:1807.037444 2018
[37] Erlin Pan and Zhao Kang. Multi-view contrastive graph clustering, In NeurlPS, volume 34, pages 11599, 2021.
[38] Chanyoung Park, Donghyun Kim, Jiawei Han, and Hwanjo Yu. Unsupervised attributed multiplex network embedding. In AAAI, pages 5371-5378, 2020.
[39] Liang Peng. Yujie Mo, Jie Xu, Jialie Shen, Xiaoshuang Shi, Xiaoxiao Li, Heng Tao Shen, and Xiaofeng Zhu. Grle: Graph representation learning with constraints. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[40] Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In WWW, pages 259-270, 2020.
[41] Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In SIGKDD, pages 701-710, 2014.
[42] Uri Shaham, Kelly Stanton, Henry Li, Ronen Basri, Boaz Nadler, and Yuval Kluger. Spectralnet: Spectral clustering using deep neural networks. In ICLR, 2018.
[43] Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:7811.0586. 2018.
[44] Chuan Shi, Binbin Hu, Wayne Xin Zhao. and S Yu Philip. Heterogeneous information network embedding for recommendation. JEEE Transactions on Knowledge and Data Engineering, 31(2):357-370, 2018.
[45] Chuan Shi, Yitong Li, Jiawei Zhang, Yizhou Sun, and S Yu Philip. A survey of heterogeneous information network analysis. IEEE Transactions on Knowledge and Data Engineering, pages 17-37, 2016.
[46] Zhiquan Tan, Yifan Zhang, Jingqin Yang, and Yang Yuan. Contrastive learning is spectral clustering on similarity graph. In ICLR, 2024.
[47] Chang Tang. Zhenglai Li, Jun Wang, Xinwang Liu, Wei Zhang, and En Zhu. Unified one- step multi-view spectral clustering. IEEE Transactions on Knowledge and Data Engineering. (566):644-66400 2022.
[48] Yijun Tian, Kaiwen Dong, Chunhui Zhang, Chuxu Zhang, and Nitesh V. Chawla. Heterogeneous graph masked autoencoders. AAAI, pages 9997-10005, 2023.
[49] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(1 1), 2008
[50] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, pages 1-12, 2018.
12

---

[51] Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liø, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR, pages 1-17. 2019.
[52] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395-416. 2007.
[53] Qi Wang, Zequn Qin, Feiping Nie, and Xuelong Li.
Spectral embedded adaptive neighbors clustering. IEEE Transactions on Neural Networks and Learning Systems, pages 1265-1271, 2018.
[54] Song Wang and Jeffrey Mark Siskind. Image segmentation with ratio cut. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(6):675-69)) 2003.
[55] Xiao Wang, Deyu Bo, Chuan Shi, Shaohua Fan, Yanfang Ye, and Yu Philip. A survey on heterogeneous graph embedding: methods, techniques, applications and sources. IEEE Transactions on Big Data, 9(2):415-436, 2022.
[56] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S. Yu. Hetero- geneous graph attention network. In WWW, pages 2022-2032, 2019,
[57] Xiao Wang, Nian Liu, Hui Han, and Chuan Shi. Self-supervised heterogeneous graph neural network with co-contrastive learning. In SIGKDD, pages 1726-1736, 2021.
Li. [58] Zehong Wang. Li, Donghua Yu, Xiaolong Han, Xiao-Zht Gao, and Shigen Shen. Heteroge-
neous graph contrastive multi-view learning. In SDM, pages 136-144, 2023.
[59] Fang Wu, Dragomir Radev, and Stan Li. Molformer: Motif-based transformer on 3d heterogeneous molecular graphs. In AAAI, volume 37, pages 5312-5320, 2023.
[60] Lirong Wu, Haitao Lin, Cheng Tan, Zhangyang Gao, and Stan Z Li. Self-supervised learning
on graphs: Contrastive, generative, or predictive. IEEE Transactions on Knowledge and Data Engineering, pages 1-20, 2021.
[61] Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self-supervised learning for graphs. In NeurlPS, 2022.
[62] Liang Yang, Cheng Chen, Weixun Li, Bingxin Niu, Junhua Gu, Chuan Wang, Dongxiao He, Yuanfang Guo, and Xiaochun Cao. Self-supervised graph neural networks via diverse and interactive message passing. In AAAI, pages 4327-4336, 2022.
[63] Liang Yang, Runjie Shi, Qiuliang Zhang, Zhen Wang. Xiaochun Cao. Chuan Wang, et al. Self-supervised graph neural networks via low-rank decomposition. In NeurlPS, 2024.
[64] Xihong Yang, Jin Jiaqi, Siwei Wang, Ke Liang, Yue Liu, Yi Wen, Suyuan Liu, Sihang Zhou, Xinwang Liu, and En Zhu. Dealmve: Dual contrastive calibration for multi-view clustering. In ACM MM, pages 337-346, 2023.
[65] Xihong Yang, Yue Liu, Sihang Zhou, Siwei Wang, Wenxuan Tu, Qun Zheng, Xinwang Liu, Liming Fang, and En Zhu. Cluster-guided contrastive graph clustering network. In AAAI, pages 10834-10842, 2023.
[66] Xu Yang, Cheng Deng, Feng Zheng, Junchi Yan, and Wei Liu. Deep spectral clustering using dual autoencoder network. In CVPR, pages 1066-4075 2019.
[67] Xingtong Yu, Yuan Fang, Zemin Liu, and Xinming Zhang. Hgprompt: Bridging homogeneous and heterogeneous graphs for few-shot prompt learning. In AAAI, pages 16578-16586, 2024.
[68] Zhaoning Yu and Hongyang Gao. Molecular representation learning via heterogeneous motif graph neural networks. In ICMI., pages 25581-255994 2022.
[69] Rui Zhang, Arthur Zimek, and Peter Schneider-Kamp. A simple meta-path-free framework for heterogeneous network embedding. In CIKM, pages 2600-2609, 2022.
[70] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Costa: Covariance- preserving feature augmentation for graph contrastive learning. In SIGKDD, pages 2524-2534, 2022.
[71] Jianan Zhao, Xiao Wang, Chuan Shi, Binbin Hu, Guojie Song, and Yanfang Ye, Heterogeneous graph structure learning for graph neural networks. In AAAI, pages 4697-4705, 2021.
[72] Sheng Zhou, Kang Yu, Defang Chen, Bolang Li, Yan Feng, and Chun Chen. Collaborative knowledge distillation for heterogeneous information network embedding. In WWW, pages 1631-1639, 2022.
13

---

[73] Sihang Zhou, Xinwang Liu. Jiyuan Liu, Xifeng Guo, Yawei Zhao, En Zhu, Yongping Zhai, Jianping Yin, and Wen Gao. Multi-view spectral clustering with optimal neighborhood laplacian matrix. In AAAI, pages 6965-6972, 2020.
[74] Yanqiao Zhu, Yichen Xu, Hejie Cui, Carl Yang, Qiang Liu, and Shu Wu. Structure-enhanced heterogeneous graph contrastive learning. In SDM, pages 82-90, 2022.
[75] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006. 201::20006.0111,, 2020.
[76] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, pages 2069-2080 2021.
14

---

A Related Work
This section briefly reviews topics related to this work, including self-supervised heterogeneous graph learning in Section A.I, and spectral clustering in Section A.2.
A.1 Self-Supervised Heterogeneous Graph Learning
In recent years, self-supervised heterogeneous graph learning (SHGL) has emerged as a helpful tech- nique deal with the heterogeneous graph that consists of different types of entities without needing labeled data [56, 60, 57, 55, 39, 23, 67J. As a result, SHGL captures meaningful representations of nodes and edges, enabling better performance in downstream tasks like node classification and node clustering. Due to its powerful capability, SHGL has been applied to various real applications, such as social network analysis [22. 62, 10], and recommendation systems [44, 17, 15].
Existing SHGL methods can be broadly classified into two groups, i.e., meta-path pattaa-at--beeed based methods and adaptive-gne Seapptive-rrph--bee graph-based methods. In meta-path- butth methods, several graphs usually constructed based on different pre-defined meta-paths to examine diverse relationships among nodes that share similar labels [18, 74]. For example, STENCIL [74] and HDMI [18] construct meth-path- -batd graphs and then conduct node-level consistency constraints (e.g., contrastive loss) between node representations in different graphs. In addition, HGCML [58] and CPIM [31] propose maximize the mutual information between node representations from different meta- meea--path-based graphs. How- ever, pre-defined meta-paths in these methods generally require expert knowledge and prohibitive computation costs [69]. Therefore, adaptive-graph-base methods are proposed to learn the adaptive graph structures to capture the relationships among nodes that possess the same label, instead of using meta-paths. For example, recently, HERO [30] made the first attempt to learn an adaptive self-expressive matrix to capture the homophily in the heterogeneous graph, thus avoiding meta-paths.
Although existing SHGL methods (especially the adaptive-graph. based methods) have achieved impressive performance in several tasks, the learned graph structure cannot be guaranteed optimal. As a result, the learned graph structure may contain noisy connections from different classes to affect the message-passing process and weaken the discriminative information in node representations.
A.2 Spectral Clustering
Spectral clustering partitions data points into clusters based on a similarity matrix derived from the data [53, 47, 65]. Owing to its proficiency in identifying clusters with complex shapes and handling non-linearly separable data, spectral clustering is widely used in many scenarios [73, 24, 26, 64].
The spectral clustering methods can be broadly classified into two groups, i.e., traditional spectral clustering and deep spectral clustering. Traditional spectral clustering methods aim to group data points that are similar to each other while being dissimilar points in other clusters by eigendecom- position [34, 35]. For example, CAN [34] proposes to learn the data similarity matrix and clustering structure simultancously with the cigendecomposition. SWCAN [35] further assigns weights for different features to learn the similarity graph and partition samples into clusters simultancously. Despite its effectiveness, traditional spectral clustering generally requires expensive computation costs, especially for large datasets. To alleviate this issue, deep spectral clustering methods have been proposed in recent years. For example, DSC [66] employs an encoder and two decoders to train the network, thus obtaining discriminative representations for clustering and implementing the cluster assignment via the neural network. DSCL [21] introduces a novel metric learning framework that leverages spectral clustering principles, thus reducing complexity to linear levels. Spectral- Net [42] proposes to learn a mapping function via the orthogonalization network to address the out-of-sample-extenee
and scalability problems.
The above methods conduct spectral clustering explicitly. Surprisingly, recent research shows that some popular self-supervised methods also implicitly conduct spectral clustering [7, 46]. For example, [7] demonstrates contrastive learning performs spectral clustering on the population augmentation graph by replacing the standard InfoNCE [36] with its proposed spectral contrastive loss. [46] demonstrates that contrastive learning with the standard InfoNCE loss equivalent to spectral clustering on the similarity graph. Although these methods make efforts to connect previous self- supervised methods with spectral clustering, they cannot be easily transferred to SHGL. First, these methods are almost based on the augmentation graph, which assumes that different augmentations
15

---

of the same sample connect each other and thus form a graph. In contrast, in SHGL, there is no augmentation. and the graph constructed by connecting different samples. Second, compared to the above methods, SHGI. incorporates the message-passing process, which makes it more complex. Therefore, connecting SHGL, methods with the spectral clustering remains challenging.
B Algorithm and Complexity Analysis
This section provides the pseudo-code of the proposed method in Section B.1, and the complexity analysis of our method in Section B.2.
B.1
Algorithm
Algorithm The podudo-code of the proposed method.
Input: Heterogeneous graph G = (V, E, X, T,R), R), non-negative parameters 3, 7, 7 P and o;
Output: Encoders Ge. fe:
1: Initialize parameters;
2: while not converge do
3: Obtain semantic representations H with encoder Jş:
4: Obtain the closed-form solution of the affinity matrix by Eq. (10);
5: Obtain the orthogonal cluster assignment matrix Y by Eq. (11) and Eq. (12); Conduct the spectral loss based on Y and by Eq. (13);
6:
7:
Obtain node representations Z by Z SH;
8:
Obtain heterogeneous representations with encoder fo:
9:
Project node and heterogeneous representations into latent space to obtain Q and Q:
10:
Conduct the node-level consistency constraint between Q and Q by Eq. (16);
11:
Obtain cluster representations Q by Eq. (17);
12:
Conduct the cluster-level consistency constraint between Q and Q by Eq. (18);
13:
Compute the objective function J by Eq. (19);
14:
Back- proc-propagate J to update model weights;
15:
end while
B.2
Complexity Analysis
Based on the Algorithm above, we then analyze the time complexity of the proposed method. Recalling Eq. (10) in the main text:
Si (- d. A)+:
(21)
2a
where d. h: h B|1 f I where H E Raxd and F E R are semantic representa- tions and eigenvector matrix, and indicate number of dimensions and classes, and n indicates the number of nodes. To reduce the computation costs, the proposed method proposes to only calculate S, between node v; and its k nearest neighbors. Therefore, the time complexity of Eq. (21) is Onnk). Moreover, the proposed method proposes to replace the eigendecomposition with projection head and orthogonalization layer to further reduce the time complexity. Specifically, the time complexity of the orthogonal process for H and Y with the QR decomposition is O(nd)) and Onne2), respectively. The time complexity of the inversion process in Eq. (12) for H and is (dd) and (c²²). Moreover, the time complexity of the spectral loss is O(nkc) and the time complexity of Z = SH is O(ndd). In addition, the time complexity of node-level and cluster-level consistency constraints
O(nd²) and O(n), respectively. Therefore, the overall complexity of the proposed method is Ondd + nc² + nkd + nke + d + c²) in each epoch, where d? c² < n, thus is scaled linearly with the sample size.
C Proofs of Theorems
This section provides definition, detailed proofs of Theorems, and derivation process Section including the proofs of Theorem 2.2 in Section C.I. the proofs of Theorem 2.3 in Section C.2, the
16

---

proofs of Theorem 2.5 in Section C.3, the proofs of Theorem 2.6 in Section C.4, the derivation of Eq. (7) in Section C.5, the derivation of the closed-form solution and parameters in Section C.6, and the derivation of the orthogonalization in Section C.7.
C.1 Proof of Theorem 2.2
Theorem C.1. (Restating Theorem 2.2 in the main text). Assume the learned representations H are orthogonal, optimizing previous meta-path-bbrd and wddptive-graph-basse graph-based SHGL methods is equivalent to performing spectral clustering with additional regularization, i.e.,
min Lsnar. = min Tr(H"LH) LH) + R(H) s.l., H II
(22)
where R(-) indicates the regularization term, L indicates the Laplacian matrix the meta veeta-path-bere path-based graph or the adaptive graph structure.
Proof. First, prove the connection between previous meta-patt--asse SHGL methods and spectral clustering. To do this, take a heterogeneous graph with two meta paths as an example, we let = (g U g(2) indicates the union of meta-path- pased graph views. Moreover, we denote the representations of previous methods before the message- pessssggggssingggggg H (generally obtained by linear mapping from original node features). addition, we denote the node representations of different graph views after the message-paseee -aasgggg as (rr), respectively, where 1,2, i.e.
= h, + (hy, 1y E {N())
(23)
where (r) indicates the hop neighbors of node v, in the r-th reeta-ptth-bssee graph.
Based on the node representations ((r of each graph, previous meta-ppth-bor SHGL methods generally propose to extract the invariant information among node representations from different meta-path- sita-ppth-basedd graphs. Here, we take the Mean Squared Error (MSE) loss as a simple example to extract the invariance and then conduct an analysis of previous peeta-path-ber path- SHGL methods. Therefore, the objective function of previous meta- path path-based SHGL methods can be formulated as:
min
2, 112.
(2)
(24)
Based on Eq. (23), rewrite Eq. (24) as:
|z]" (1) 21 1
min
0
min
[b; + (h E ((())) h. --,,, ux E (2,1))
min
[h; (ha th E (.(()) + (hy, (N( -h.12
min
Σ |b; - (hr, un E (((()) HI + I1b,, (N((:)) - -hil1
(25)
+ Σ
(h; (hg, u4 (N( ((h,, E (N)))) -h,))
n
min
Σ
g lh; hull >Σ h, h
+ >
(hh (hg, uk E (11) ((h,, (())) h.))
min Σ
Σ Guillh; hil1 +2 Σ
((h: (hE, 2u E (c)))
((h, E (Nv) hz)).
17

---

Denote D as the degree matrix of G, denote L = G as the graph laplacian, and denote h' E IR" h, E IR the i-th column and j-th row of H, according to the spectral graph analysis in [52]. we further have
(h')"L(h')= = (h') gh')
-
(h Σ
h
j=l
sk==1
(26)
d3 (h - -
h h h ik gyk +
dde
das (h th )2)
2 ,=1
1,k=1
k=
Σ
93 2
2
JAk=1
Therefore, further have
d
n
Σ hh')
Lh')'((h))
= Σ
Gjk
_ i=1
(h h.
(27)
2
j.k=1
That is
n Σ
Tr(H LH)
gyal h,
h&
(28)
jik=1
where Tr(-) indicates the matrix trace. Therefore, based on Eq. (25) and Eq. (28), we can obtain
min z: 2.2112
min 2Tr HTr(H" LH) + Σ ((h, - (hg. uh ( (hy. E ((()) -h,))) (29)
0
n
min 2Tr LH) 2
Σ Gr hy) (h, hb)))
k.j.k
Based on the assumption that H = I, we can conclude that previous meta-path-bassd SHGL methods, which extract the invariance among different graphs, equals the known spectral clustering with additional regularization. Note that the MSE loss in the above example can be replaced by other contrastive or non-contrastive loss (e.g. InfoNCE [36]), and can easily obtain similar results.
After that, we further prove the connection between recent adaptive-gran -rr-g-rapphhhah graph-based based SHGL methods [30] and the spectral clustering. Denote the self-expressive matrix in [30] S, and denote the representations after projection by linear transformation as H. Moreover, denote Dş as the degree matrix of S and denote Ls Ds S as the graph Laplacian. Given that the self-expressive matrix is symmetrical and non-negative, the objective function of previous adaptive-graph-basse SHGL methods can be formulated as:
min H - HHH-HHI 0,5
Σ duyS + 3
(30)
1
1,j=1
where a and 33 are non-negative parameters, and dis indicates the distance among nodes based on H original node features. Based on the self-expressive constraint in the first term of Eq. (30), we have
h
Σ j=1
(31)
Therefore, for any h, where i E [1, n), we further have
h h;
Σ
syy hy
(32)
j=1
18

---

Based on the constraint s 1 = 1, we obtain
Sig h h, =2 Σ
hy
(33)
j=1
J=1,53
Therefore, the constraint in Eq. (31) can be transformed as:
Sij + Σ
Siy h h, - 2
Σ
5,yh hj =
(34)
j=1
1=1
In addition, we further have
Σ
Sij
+
Sty
h h,
-2
Σ
hiyh, hy) =
Sty
h, h S.y.
(35)
:=1
j=1
==1
i i=1,iyh
1=1
Similar to the proof above, also rewrite Eq. (30)
min (TTTHHLLHH + 0,5
dysSy +
(36)
1,f=1
Based on the assumption that H we can also conclude that previous adaptive-graph-based SHGL methods are equal to the known spectral clustering with additional regularization. Therefore, we complete the proof.
C.2 Proof of Theorem 2.3
To prove Theorem 2.3, first give the definition of the graph-cut algorithm as follows. Definition C.2. (Graph-Cut) For a given number k of subsets, the mincut approuch simply consists in choosing a partition Vi,..., Va which minimizes
1
Cut (V Va)
W
(Vi, Vi).
t=1
(37)
1
W (V.
Cut (V, V.) [4]
RatioCut (Vi....,, Vi)
2
Vi
where (V., Vo.) = Eiev.sev, Wij indicates the weight between different subsets, and V is the complement V.
Theorem C.3. (Restating Theorem 2.3 in the main text). Under the same assumption in Theorem 2.2, optimizing previous meta--path-ben based and adaptive- ceattive-graph-Bee graph-based SHGL methods is approximate to performing the RatioCut (V1,...,VV, algorithm that divides the learned representations into partitions (Vi...., Va), ie.,
min Cshar. 2 min RatioCul (V,,...,Va)
(38)
where d indicates the dimension of representations H.
Proof. Given partition of V with samples into sets Vi,..,, Va. we first define dl indicator vectors hy = (hi.j...., ha.) by
1/VlV {
if E V otherwise
b
(i=1.
n:j l,..,.
(39)
Then we set the matrix H Raxdd as the matrix containing those d indicator vectors as columns. Observe that the columns in H are orthonormal to each other, i.e., H HH I, where I is the identity
19

---

matrix. Denote L as the unnormalized graph Laplacian, according to [52], we can obtain
hf Lh, = 2
Σ
(h hR)
Jakm1
2
1
E
V
V [
Σ
VV
V
wyR
wik
M
[
JEV,
JEV
(40)
[Vdl
[VI
cV,, V.)
[V
[V
[V
+ IV.
V1 + V7
= cut(V,, V.)
[V]
MI
= [V] RatioCut Vi, V.).
Moreover, we have h. Lh; (H" (H) Therefore, we have
d Σ LH)
LHH"LH)
EbTTh, = RatioCut (Vi,..., Va),
(41)
i=1
==1
where Tr(-) indicates the trace of a matrix. Therefore, minimizing the RatioCut (Vi...., Vi.) can be transferred
min V
Tr(H" LH) s. s.t. H I, H as defined in Eq. (39).
(42)
Then we consider relaxing the constraints of the problem by allowing the entries of the matrix to assume arbitrary real values. As result, the problem is transformed into relaxed version:
min
(H (H LH) s.t., H'
(43)
HERoXd
This the standard spectral clustering, as we mentioned above. Therefore, we can obtain that conducting spectral clustering is approximating conducting the RatioCut algorithm. which divide the learned representations into partitions, where indicates the dimension of representations. Thus, complete the proof.
C.3 Proof of Theorem 2.5
Theorem C.4. (Restating Theorem 2.5 in the main text). Optimizing the spectral loss Lap leads to performing the spectral clustering based the affinity matrix S with connected components and conducting RatioCut (V.....,V, Ve) algorithm to divide the learned representations into e partitions, i.e.,
min Cp = min Tr TY = min RatioCut(V
(44)
Proof. According Ky Fan's Theorem [5], the spectral loss Lup can be written
Lup
Σ Siz lly; - --,11 -
n²
1,1=1
(45)
2 Tr Ls -
n²
Therefore, optimizing the proposed method with Exp is equivalent to performing the spectral cluster- ing with additional regularization.
Note that, under the orthogonal constraint, the minimum of Cap is attained when the column space of Y is the subspace of the cigenvectors corresponding the smallest eigenvalues of Lg. In other
20

---

words, the learned Y can perfectly fit the cigenvectors when the minimum of Lsp is attained. Recall the objective function the main text, i.e.
ming.F Σmj=1 h; h + as + B - f51/ 8.g) S.L., Vi, 5 = 1.0 S. 1
(46)
Therefore, when the minimum of Cap attained, the constraints in the above function can be satisfied, iee. rank(Ls) = holds. As result, we can obtain the affinity matrix S with exactly connected components.
Moreover, according to the Theorem C.3, we have
Tr D(Y'LSY) Σ yt Lsy: RatioCut (Vi...., Vi)
(47)
That is, the proposed method divides the learned representations into partitions, where indicates the number of classes. Thus, we complete the proof.
C.4 Proof of Theorem 2.6
We first follow previous works [33] to define the Complexity Measure to evaluate the generalization ability of neural networks based on the Davies Bouldin Index.
Definition C.5. (Complexity Measure) The complexity measure of neural networks can be defined as:
S. S.+SJ
C
max (F Mi.j
(48)
where
m: O p4i (P) 1/2 for = 1...
S.
1 Σラ
(49)
M1. = 1|m4 μ l1z for i,j = 1...k
i and j are indices of two different classes, O!T)) the output representation of the T-th sample belonging to class i for the given model, μii is the cluster centroid of the representations of class S; a measure of scatter within representations of class i, and Ms, is a measure of separation between representations of classes i and j.
Morcover, we further follow previous works [33, 16] to define the generalization bound G of a model based on the model complexity, i.e.,
Definition C.6. (Generalization Bound) For any 8 E [0, 1]. with probability at least 1 - 8, the generalization bound G of a model follows the inequality, i.c..
1 G Σ ((f(x)))))) + v=r OVV log(1/5)
C
(50)
where (x;, is a pair of labeled data, f is the model, is the loss function, n is the number of labeled data, C the model complexity measure.
Based on the Definitions above, we can derive the Theorem as follows.
Theorem C.7. (Restating Theorem 2.6 in the main text). The proposed method with dual consistency constraints achieves lower boundary the model complexity C and higher generalization ability boundary G than previous SHGL with the node-level consistency constraint only, i.e.
inf (CSCHOOL) inf(CsH))). sup(GscHooL)) > sup(GsHGL),
(51)
where in) and sup(-) indicates lower bound and upper bound, respectively.
Proof. We take the binary classification as example, Eq. (48) can be rewritten the heterogeneous representations Z learned by the heterogencous encoder, obtain its cluster
So Mo.1
Then, for
21

---

centroid Ho:
E Xxx) (EN((1))
140 B[Z.] (X
(52)
= W (Po Mx. + (1 Po) -x,),
where (v:) indicates the neighbors of v; from other type of nodes, W indicates the parameters of the heterogeneous encoder, MXx, indicates the cluster centroid of the node features of class i, PX, indicates the cluster centroid of the node features of other types of nodes. Similarly, we further have:
M1 W (Pi px, + (1 Pi) ,xx,)
(53)
where ,X, indicates the cluster centroid of the node features of other types of nodes. Therefore, we can obtain
Mo,1 I1 M1ll
(54)
W (Po MXx + + (1- -o),,x px, PI px. - - Pi) -.)-,xx)))
(xx))l
Moreover, have
$ = Billo - Hol 1 = E [< 0 - Mo, - Hu >] P W (x. |xx) 11 + (1 Po) BalFEllxxX |xx, )}
-o.
(55)
where < <.. > inequality, i.e.
inner production. To rewrite the above function, we first derive the following
bc + (1- b+c'
(56)
where 0- S S 1, and 0 < c.c. To prove the inequaility in Eq. (56), we construct function f(a) = a²b + (1 - a)²c-
be We then take the derivative of f(a), i.e.,
b+ce
f((a) 2ab
2c + 2ac
(57)
Then let f'(a) 0, and have a
e btc
We have
b
be
be
f(
b+c 0.
(58)
(b + cj2
(b + c)²
In addition, we take the second-order derivative of (a) and obtain
f"(a) 2(b + c) 2 O.
(59)
Therefore, [a) is decreasing when < - and increasing when > 8:o. and reaches its minimum 0 at sFc. As result, f() 0 always holds for 0 I a S 1. Thus, we prove the inequality in Eq. (56).
Given the above inequality in Eq. (56), for Eq. (55), we let of EX -xx,) 12) of (X - px, xxx) 11 of [i|l w (X - μ,x ,xx,))l | and of = E[| (X ,xx, ,xx))11) 112). Moreover, we replace a, b, and e in Eq. (56) with Po. of and o7. respectively. Then Eq. (55) can be rewritten as:
añoz $8 = P.g (1 Po) 0 t
(60)
Similarly, we can also reach the following inequality:
of of + +
P1) oz =
(61)
Therefore, the complexity measure can calculated by:
C / S
Vat+o
Va o
(62)
Ma.1
Mo.1
22

---

Note that the cluster-level consistency constraint minimizes the first term in the Sg and Si (i.e., of and of). Moreover, we can observe that Eq. (60) and Eq. (61) are the increasing function with respect to and Ø1 Therefore, minimizing the cluster-level consistency constraint is equivalent to minimizing the lower bound of the model complexity. Therefore, the lower bound complexity measure C of the model with the dual consistent constraints is less than the model without it, i.e. iscoOo)) < inf(CsHGL). As a result, according to [33], we can conclude that the representations learned by the dual consistent constraints have higher bound of generalization ability than previous methods with instance-level constraint only, i.e., sup(GscHoor.) > sup(GsHGL) thus complete the proof.
C.5 Derivation of Eq. (7).
Recalling Eq. (7), i...
Σ (Ls) min Tr(FF LgF) F=F-I
min
Σ Siy ||f. - fyll F= 2
(63)
F F
where Raxe is the cigenvector (i.e. F 1) of Lş corresponding to the c eigenvalues. We first derive the first equation. The eigendecomposition of the symmetric Lg can be written as: Lg BAB"" where is the eigenvector matrix and A is the diagonal matrix whose diagonal elements are the eigenvalues of Lg. We have:
Tr(F"LgF) Tr(
Ls ( fi fo
fo)
Lih
Lsl E Lsf
Ls
(64)
f Lsf
E Lsfo
= =Tr(
p Lsf
LsL
r Lsfe
- 1==1 A.
where Ei=1 A; indicates the sum of any ceigenvaluss of Lg. Obviously, minprg=r Tr(F"Lggh achieves minimization when F is the eigenvectors corresponding e smallest eigenvalues. Therefore we have mins Σi=1 (Ls) minprg-1 Ir(F= LşF) and the first equation in Eq. (63) proved. Moreover, based Eq. (26)-Eq. (28), we can further complete the proof the second equation in Eq. (63).
C.6 Derivation of the Closed-Form Solution and Parameters.
We first obtain the Lagrangian function of the objective function in Eq. (9) in the main text:
C(s;, A, = |ss + 2a d, 2 A(s - - -
(65)
where À and E, 2 0 are the Lagrangian multipliers. Based the KKT condition [3], obtain the closed-form solution of the above Lagrangian function, i.e.,
Sij = (- 20;
di + Ac)+,
(66)
where (-)+ indicates max{-, 0}. For the sparse affinity matrix S, each vector contains k nonzero elements only. Therefore, have Si 0 and S That is, 2a, di + A; > and
2o0 d + > S 0. Then based on Eq. (66) and the constraint s = 1, we further have
1
dij + +x) = -1
(67)
2a
j=1
23

---

Table Statistics of all datasets.
Datasets
Type
#Nodes
#Node Types
#Edges
#Edge Types
Target Node
#Training
#Test
ACM
Heter
8,994
3
25,922
4
Paper
600
2,125
Yelp
Heter
3,913
4
72,132
6
Bussiness
300
2,014
DBLP
Heter
18,405
3
67,946
4
Author
800
2,857
Aminer
Heter
55,783
153,676
4
Paper
1,000
Photo
Homo
7,650
238, 162
2
Photo
6,120
Computers
Homo
13.752
491.722
2
Computer
1,375
11,002
Therefore, we obtain X
+ 3ka;
Σj=1 dij. Moreover, we have the following inequality for oi.
i.e.,
k
k di or
k d i++1
1
d
(68)
2
2
2 j=1
Hence, achieve an optimal solution s; contain precisely non-zero values, we can set Og as:
k
a; d
de
(69)
2
Then the overall a could be set to the mean of ai, a2 ..... On.
Then can be obtained by:
d
dgj)
(70)
C.7
Derivation of the Orthogonalization
Recalling Eq. (12) in the main text:
Y = nP [R R)-),
(71)
where P the cluster assignment matrix, and R is a upper triangular matrix obtained from the QR decomposition P = ER and ETE I. Then we have
P RR E.
(72)
We further have
YTY = nE
(73)
nl.
Therefore, we can obtain that Y is orthogonal.
D Experimental Settings
This section provides detailed experimental settings in Section Experiments, including the description of datasets Section D.I, summarization of comparison methods in Section D.2, evaluation protocol in Section D.3, model architectures and settings in Section D.4, and computing resource details in Section D.5.
D.I Datasets
We use four public heterogeneous graph datasets and two public homogeneous graph datasets from various domains. Heterogeneous graph datasets include three academic datasets (i.e., ACM [56], DBLP [56], and Aminer [I]],, and one business dataset (i.e., Yelp [71]). Homogeneous graph datasets include two datasets (i.e., Photo and Computers [43]). Table summarizes the data statisties. We list the details of the datasets follows.
24

---

ACM is an academic heterogeneous graph dataset. It contains three types of nodes (paper (P), author (A), subject (S)), four types of edges (PA, AP, PS, SP), and categories of papers as labels.
Yelp is business heterogeneous graph dataset. It contains four types of nodes (business (B), user (U), service (S), level (I.)), six types of edges (BU, UB, BS, SB, Bl., LB), and categories of businesses as labels.
DBLP is an academic heterogeneous graph dataset. It contains three types of nodes (paper (P), authors (A), conference (C)), four types of edges (PA, AP, PC, CP), and research areas of authors as labels.
Aminer is an academic heterogeneous graph dataset. It contains three types of nodes (paper (P), author (A), reference (R)), four types of edges (PA, AP, PR, RP), and categories of papers as labels.
Photo and Computers are two co-purchase homogeneous graph datasets. They are two networks extracted from Amazon's co-purchase data. Nodes are products, and edges denote that these products were often bought together. Products are categorized into several classes by the product category.
Table 4: The characteristics of all comparison methods.
Methods
Hetero
Homo
Semi-sup
Self-sup/unsup
Meta-path
Adaptive
DeepWalk (2014)
GCN (2017)
GAT (2018)
DGI (2019)
GMI (2020)
MVGRL (2020)
GRACE (2020)
GCA (2021)
G-BT (2022)
COSTA (2022)
DSSL (2022)
LRD (2023)
Mp2vec (2017)
HAN (2019)
HGGT (2020)
DMGI (2020)
DMGlatta (2020)
HDMI (2021)
HeCo (2021)
4
HGCML (2023)
CPIM (2023)
HGMAB (2023)
HERO (2024)
SCHOOL (ours)
D.2
Comparison Methods
The comparison methods include eleven heterogeneous graph methods and twelve homogeneous
graph methods. Heterogencous graph methods include Mp2vec [4], HAN [56], HGT [13], DMGI
[38]. DMGIattn [38], HDMI [18], HeCo [57], HGCML [58], CPIM [31], HGMAE [48], and HERO
[30]. Homogeneous graph methods include GCN [20], GAT [50], DeepWalk [41], DGI [51], GMI
[40], MVGRL [8], GRACE [75], GCA [76], G-BT [2], COSTA [70]. DSSL [61], and LRD [63]. The characteristics of all methods are listed in Table 4, where "Hetero" and "Homo" indicate the methods designed for the heterogeneous graph and homogeneous graph, respectively. "Semi- sup", and "Self-suup'unsp" indicate that the method conducts semi-supervised learning, and self- superviseedunsupervisss learning, respectively. "Meta-path" indicates that the method requires pre-defined meta meta-paths during the training process. "Adaptive" indicates that the method learns an adaptive graph structure instead of traditional meta-paths.
25

---

Table Settings for the dimensions of encoders (i.e., 96 R/xds and fo fxd1) and projection heads (i.e., Pv Rdixe xe and 9, E Rd x on all datasets.
Settings
ACM
Yelp
DBLP
Aminer
Photo
Computers
1,902
82
334
128
745
767
d1
512
256
128
256
1024
1024
d2
64
256
256
256
256
256
3
3
4
4
8
10
Table 6: Clustering performance (i.e., NMI and ARI) of all methods on heterogeneous graph datasets.
ACM
Yelp
DBLP
Aminer
Method
NMI
ARI
NMI
ARI
NMI
ARI
NMI
ARI
DeepWalk
41.6+t0.5
35.3+2..6
35.1
37.7+1.1
69.0=0.2
73.3++0.3
26.2.+0.3
2..4+0.4
Mp2vee
21.4+0.7
21.1
38.9+0.6
39.
73.5=0.4
77.7+0.6
30.4=0.4
25.5+0.6
DMGI
67.8:10.9
70.2.11.0
36.8.0.66
34.410.7
72.2.0.88
72.810.9
27.3.10.9
23.1110.8
DMGlattn
70.2++0.3
72.5=0066
38.1
40.2+00.6
69.6#0.6
73.9+0.4
28.3=0.3
25.5
HDMI
69.5:00.5
72.3+0.7
38.910.6
40.7=008
73.1=0.3
74.410.4
33.5=0.4
28.9=0.5
HeCo
67.810.8
70.5
39.310.6
42.1
74.5=0.8
80.1+0.9
32.2=1.1
28.6+1.0
HGCML.
69.1400.7
71.6+0.88
37.4+0.6
39.5+0.88
74.5+00.
75.1+:111
35.940.66
31.1+0.5
CPIM
68.6+00.3
70.8+0.5
40.1+0.8
42.1+0.9
73.7+00.5
78.0+00.
35.8+0.5
30.1+00.7
HGMAR
69.7+.0.8
72.6+-0.6
40.3+0.9
42.4+0.8
76.9+0.6
82.3+00.7
41.1+0.8
38.3+0.9
HERO
68,8110.6
71880..6
38.610.8
40.6110.9
74.1-00.
79.310.7
36.8-0.7
35.310.9
SCHOOL
69.6110.7
72.110.5
41.21099
43.5.10.6
77.110.6
82.510.5
42.410.6
38.810.8
D.3
Evaluation Protocol
We follow the evaluation in previous works [18, 37, 72] to conduct node classification and node clustering as semi-supervised and unsupervised downstream tasks, respectively. Specifically, we first train models with unlabeled data self-supervised manner and output learned node representations. After that, the resulting representations can be used for different downstream tasks. For the node classification task, we train a simple logistic regression classifier with a fixed iteration number, and then evaluate the effectiveness of all methods with Micro-Fl and Macro-F1 scores. For the node clustering task, we conduct clustering and split the learned representations into clusters with the K-means algorithm. then calculate the normalized mutual information (NMI) and average rand index (ARI) to evaluate the performance of node clustering.
D.4 Model Architectures and Settings
As described in Section 2, the proposed method employs the MLP (i.e., 9q) and the closed-form solution of the affinity matrix to obtain node representations Z. Moreover, the proposed method employs the heterogeneous encoder (i.e., fo) obtain heterogeneous representations Z. In addition. the proposed method employs the projection head Ptp to obtain the cluster assignment matrix P. After that, the proposed method employs projection head d, to map the node representations and heterogeneous representations into latent spaces. In the proposed method, projection head Pe and Qy are simply implemented by the linear layer, followed by the ReLU activation. We report the settings for the dimensions of encoders in Table 5. Finally, In the proposed method, all parameters were optimized by the Adam optimizer
[19] with an initial learning rate. Moreover, We use early stopping with patience of 30 train the proposed SHGL model. In all experiments, repeat the experiments five times for all methods and report the average results.
D.5 Computing Resource Details
All experiments were implemented in PyTorch and conducted on server with 8 NVIDIA GeForce 3090 (24GB memory each). Almost every experiment can be done on an individual 3090, and the training time of all comparison methods as well as method, is less than I hour.
26

---

Table 7: Classification performance (i.e.,
Macro-F1 and Micro-F1) homogeneous graph datasets.
Photo
Computers
Method
Macro-Fl
Micro-Fl
Macro-F1
Micro-F1
DeepWalk
87.4+:0.5
89.7+-0.3
84.0:10.3
85.6++0.4
GCN
90.510.3
92.5+0.2
84.010.4
86.410..3
GAT
90.2:10.5
918210.
83.210.2
85.710..
DGI
89.3+00.2
91.6+0.3
79.3+-0.3
83.9+0.5
GMI
89.3+00.4
90.6+0022
80.1+0.4
82.2++0.4
MVGRL
90.1.10.3
91.710..4
84.6.10.6
86.910.5
GRACE
90.3100.5
91.910.3
84.210..3
86,8
GCA
91.1110.4
92.410.4
85.910.5
87.7
COSTA
91.3=#04
92.5+0.3
86.4+0.3
88.3
DSSL
90.6+0.2
92.1+0.3
85.6+10.3
87.3
LRD
91.1=0.5
92.8+0.7
86.61:0.3
88. 88.640.6
SCHOOL
91.9-104
93.1-10.3
85.911..6
08.7
(a) HDMI (SIL: 0.36) (b) HeCo (SIL: 0.33)
(c) HERO (SIL: 0.34) (d) SCHOOL (SIL: 0.41)
Figure 3: Visualization plotted by t-SNE and the corresponding silhouette scores (SIL) of node representations of the proposed SCHOOL and other SHGL comparison methods on the DBLP dataset.
E
Additional Experiments
This section provides some additional experimental results to support proposed method, including experiments on the effectiveness of the affinity matrix in Section E. visualization of the learned representations in Section E.4, parameter analysis in Section E.5, experimental results on the node clustering task in Table 6, and experimental results on homogencous graph datasets in Table 7.
E.1 Effectiveness of the Rank- Cank-Constrained Affinity Matrix
The proposed method proposes to learn a rank-constrained affinity matrix with exact components to capture the connections within the same class while mitigating the connections from different classes. This actually shares part of similar idea with the self- self-attention mechanism, which aims to assign weights for all sample pairs. To further verify the effectiveness of the rank-constrained affinity matrix, we investigate the performance of the variants methods with the cosine similarity, the affinity matrix, the self-attention mechanism, and report the results Table
Obviously, the proposed method with the affinity matrix obtains superior performance than the cosine similarity and the self-attention mechanism on all datasets. The reason be attributed to the fact that the affinity matrix in the proposed method is constrained to contain exactly components to mitigate noisy connections from different classes. In contrast, although either the cosine similarity or self-attention mechanisms may assign small weights for node pairs from different classes, it inevitably introduces noise during the pessage-passing process affect the quality of node representations. As a result, the effectiveness of the rank-constrainde affinity matrix is verified.
E.2 Effectiveness of the Node-level Consistency Constraint
To verify the effectiveness the node-level consistency constraint, we conducted experiments to replace the proposed node-level consistency constraint with the InfoNCE loss and reported the
27

---

Table 8: Classification performance (i.e., Macro-F1 and Micro-F1) of variant methods with the affinity matrix, cosine similarity and, self-attention mechanisms on heterogeneous graph datasets.
ACM
Yelp
DBLP
Aminer
Method
Macro-Fi Fl
Micro-FI Macro-F1 Micro-F1
Macro-FI
Micro-FI
Macro-F1
Micro-Fl
cosine similarity
85.3:10.9
85.1H11.1
88.2+:0.4
87.7:10.7
89.3:10.7
90.5+
67.6=0.55
75.4:10.6
self-attention
88.7+10.8
88.44-0.7
92.0++0.5
91.7:10.6
91.2++0.4
92.1=0.6
7372=007
82.1+0.6
affinity matrix
92.7:10.6
92.6::0.5
93.010.7
92.8:0.4
94.0=0.3
94.7:00.4
77.5=0.9
86.8-0.7
Table 9; Classification performance (i.e.. Macro-FI and Micro-FI) of the node-level consistency constraint and InfoNCE loss heterogeneous graph datasets.
ACM
Yelp
DBLP
Aminer
Method
Macro-F1
Micro-F1
Macro-F1
Micro-FI
Macr--F1
Micro-F1
Macro-F1
Micro-F1
InfoNCE
91.311.1
91.2.10.8 92.611.55
92.4
92.010.8
94.110.6
94.6110.5
85,4100.3 76.8=0.4
Proposed
92.710.6
93.0.10.7
92.810.4
94.0110.3
94.7:10.4
86.8110.7 77.5=0.9
results in Table 9. From Table 9, we can find that the variant method with InfoNCE loss obtains similar performance the proposed method. However, the InfoNCE loss generally requires the time complexity of O(²²), where n is the number nodes. This may introduce large computation costs during the training process. In contrast, the proposed method simply designs the node-level consistency constraint in Eq. (15) to capture the invariant information with the time complexity of O(nd), where d is the representation dimension and generally d² <
Macro-Fi (%)
ACM
Yelp
DBLP
Amina
10
20
30
40
50
Number clusters
Figure Classification performance (i.e., Macro-F1) of the proposed method under different clusters.
E.3 Effectiveness of Different Cluster Numbers
The proposed method divides the learned representations into several clusters. Generally, the number of clusters equals to obtains better results because, in downstream tasks, it is easier to distinguish clusters than larger number of clusters. To verify it, we changed the number of clusters and reported the results in Figure 4. Obviously, the proposed method obtains the best results when the number of clusters equals to e and decreases as the number of classes increases. This reasonable because when the number of classes increases, the nodes within the same class may be assigned to different clusters, thus making difficult classify them correctly.
E.4 Visualization the Learned Representations
To further verify the effectiveness of the learned representations, we visualize node representations of the proposed SCHOOL and other SHGL. comparison methods on the DBLP dataset and report the results and corresponding silhouette scores (SIL) in Figure 3. Obviously, in the visualization.
28

---

(a) ACM
(b) Yelp
(c) DBLP
(d) Aminer
Figure 5: The classification performance of the proposed method at different parameter settings (i.e., ,l, and 8) on all heterogeneous graph datasets.
the node representations learned by the proposed method exhibit better clustering status, ie.. nodes with different class labels are more widely separated. Moreover, the representations learned by the proposed method obtain the best silhouette score, compared to other SHGI. comparison methods (i.e., HDMI, HeCo, and HERO). The reason can be attributed the fact that the proposed method conducts spectral clustering explicitly, and cuts the learned graph into components as well as further utilizes the clustering information to facilitate downstream tasks.
E.5 Parameter Analysis
In the proposed method, we employ non-negative parameters (i.e., and ô) to achieve trade-off between different terms of the final objective function J. To investigate the impact p. and d with different settings, we conduct the node classification on all heterogencous graph datasets by varying the value of parameters in the range of [10-3.10 3,103] and reporting the results in Figure 5. From Figure 5, we can find that if the values of parameters are too small (e.g.. 10 10-3), the proposed method cannot achieve satisfactory performance. This verifies that both node-level and cluster-level consistency constraints are significant for the proposed method.
29

---

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]
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
We discuss the limitations of the work Section 4.
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] We provide the assumptions and complete proof in Appendix C.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes] See Section 3 and Appendix D.
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] We released codes and data at http://ggttaa..cooooooaaaaa/////
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?
Answer: [Yes] We specify all the training and test details in Appendix D.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yss]
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes] We list the details of experiments compute resources in Appendix D.5.
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with
NeurlPS Code of Ethics https: :ttpps::///eurss.....
Answer: [Yes]
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
We discuss broder impacts in Section
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
30

---

Answer: [NA]
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]
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
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 equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
31


Reviews:
[{"review_id": "NQrBVyRZO7", "reviewer": "Reviewer_LzB2", "summary": "Overall, this paper makes the first attempt to theoretically revisit previous SHGL methods from the spectral clustering perspective in a unified manner. Specifically, this paper revisits SHGL from the spectral clustering and introducing a novel framework enhanced by rank and dual consistency constraints. Specifically, the proposed framework incorporates a rank-constrained spectral clustering method that refines the affinity matrix to exclude noise effectively. Additionally, the proposed method integrates node-level and cluster-level consistency constraints that concurrently capture invariant and clustering information to facilitate learning in downstream tasks.", "questions": "see weakness.", "limitations": "Yes, the authors have discussed the limitations and potential negative societal impact.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. I really appreciate the idea that revisiting previous SHGL methos from the perspective of spectral clustering, which is interesting and may inspire some researchers in the graph learning as well as the self-supervised learning communities.\n2. Theoretical analysis verifies the effectiveness of the proposed method, which divides the learned representations into distinct partitions based on the number of classes. Furthermore, the proposed method exhibits enhanced generalization ability than previous SHGL methods.\n3. Extensive experiments on both heterogeneous and homogeneous graphs demonstrate the effectiveness of the proposed method. Visualization and case studies further verify the claims in this paper.\n4. The proposed rank-constrained spectral clustering is novel and interesting, and it seems like can also be used to the graph structure learning in the homogeneous graph.", "weaknesses": "1. In the Introduction, the authors claim that previous methods conduct message-passing relying on meta-path-based graphs and adaptive graph structures, which inevitably include noise. Are there any real examples to better illustrate the noise in meta-path-path based graph as well as the adaptive graph structures?\n2. In the dual consistency constraints, the proposed method designs the node-level consistency constraint to capture the invariant information between the node representations and the heterogeneous representations. How about replacing the node-level consistency constraint with other common loss, such as InfoNCE [1]?\n[1] Aaron van den Oord et al., Representation learning with contrastive predictive coding.\n3. The authors design the rank-constrained spectral clustering to learn the affinity matrix for nodes belonging to the same node type. Although the visualization verifies the effectiveness of the affinity matrix, it would be better for the authors to add some ablations studies to further verify it, such as replacing the affinity matrix with a self-attention mechanism or simple cosine similarity.\n4. What are the specific processes for different downstream tasks (e.g., node classification and node clustering)? It seems like training the proposed method first, and then freezing parameters of the model and applying outputted representations for downstream tasks.\n5. The proposed method is designed for the heterogeneous graph while it can be implemented on both the homogeneous graph datasets and heterogeneous graph datasets. Is it just to replace the heterogeneous graph encoder with the graph convolutional layer? How to generate two different views for the dual consistency constraints?\n6. It would be better to add some recent works about the self-supervised heterogeneous graph learning in the related work, especially those published in the past two years.\n7. The paper needs further proofreading. For example, \n- In Eq. (17) I know $q_i$ is the i-th projected representation. What’s the $\\hat{\\mathbf{q}}_{\\mathbf{y}_i}$ actually means?\n- The definitions of some symbols need to be further determined, such as \\mathbf{I} in Definition 2.1. I guess it might represent the identity matrix. \n- Some mistakes in Table 3, the Freebase dataset should be removed from the Table.\n- The caption of Table 7 should be fixed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments on the novelty, theoretical analysis, and experimental results of our method. We are so encouraged and will try our best to address the concerns one by one.\n\n> **Q1.** Any real examples to illustrate the noise in meta-path-based graphs and adaptive graph structures?\n\n**A1.**  Yes. Actually, the noise in meta-path-based graphs and adaptive graph structures indicates the edges connected nodes from different classes. Take the academic heterogeneous graph with several node types (i.e., paper, author, and subject) as an example. For the meta-path-based graph, if an author wrote two papers belonging to different classes (e.g., \"data mining\" and \"computer vision\"), then there will be a meta-path \"paper-author-paper\" to connect these two papers. For the adaptive graph structure, if two papers belonging to \"data mining\" and \"computer vision\" share part of keywords, there also may be an edge to connect them. As a result, such noisy edges in meta-path-based graphs and adaptive graph structures connect two paper nodes from different classes and introduce confusion into node representations after the message-passing.\n\n> **Q2.** How about replacing the node-level consistency constraint with other loss, e.g., InfoNCE?\n\n**A2.** To verify the effectiveness of the node-level consistency constraint, we conducted experiments to replace the proposed node-level consistency constraint with the InfoNCE loss and reported the results in Table 1 in the uploaded PDF file. From Table 1, we can find that the variant method with InfoNCE loss obtains a similar performance to the proposed method. However, the InfoNCE loss generally requires the time complexity of $\\mathcal{O}(n^2)$, where $n$ is the number of nodes. This may introduce large computation costs during the training process. In contrast, the proposed method simply designs the node-level consistency constraint in Eq. (15) to capture the invariant information with the time complexity of $\\mathcal{O}(nd^2)$, where $d$ is the representation dimension and generally $d^2<n$. We will add the experimental results and analysis in the final version.\n\n> **Q3.** It would be better to add some ablations studies to verify the effectiveness of the affinity matrix, e.g., replacing it with the self-attention mechanism or simple cosine similarity.\n\n**A3**. In the submission, we conducted experiments to replace the affinity matrix with the self-attention mechanism and reported the results in Table 6 in Appendix E. To further verify the effectiveness of the rank-constrained affinity matrix, we further investigated to replace the affinity matrix with the simple cosine similarity and reported the results in Table 2 in the uploaded PDF file.\n\nObviously, the proposed method with the affinity matrix obtains superior performance than the cosine similarity and the self-attention mechanism on all datasets. The reason can be attributed to the fact that the affinity matrix in the proposed method is constrained to contain exactly $c$ components to mitigate noisy connections from different classes. In contrast, although either the cosine similarity or self-attention mechanisms may assign small weights for node pairs from different classes, it inevitably introduces noise during the message-passing process to affect the quality of node representations. As a result, the effectiveness of the rank-constrained affinity matrix is verified. We will add the experimental results and analysis in the final version.\n\n> **Q4.**  What are the specific processes for downstream tasks (e.g., classification and clustering)? \n\n**A4.**  We follow the evaluation in previous works [1-2] to conduct node classification and node clustering as semi-supervised and unsupervised downstream tasks, respectively. Specifically, we first pre-train models with unlabeled data in a self-supervised manner and output learned node representations. After that, the resulting representations can be used for different downstream tasks. For the node classification task, we train a simple logistic regression classifier with a fixed iteration number and evaluate the effectiveness of all methods with Micro-F1 and Macro-F1 scores. For the node clustering task, we conduct clustering and split the learned representations into c clusters with the K-means algorithm, then calculate the normalized mutual information (NMI) and average rand index (ARI) to evaluate the performance of node clustering. We will add the details about downstream tasks in the final version.\n\n[1] HDMI: High-order Deep Multiplex Infomax. WWW 2021.\n\n[2] Multi-view Contrastive Graph Clustering. NeurIPS 2021.\n\n> **Q5.** Is it just to replace the heterogeneous graph encoder with the graph convolutional layer to implement on homogeneous graph datasets? How to generate two different views for the dual consistency constraints?\n\n**A5**.  Yes, we replace the heterogeneous graph encoder with the graph convolutional layer to implement the proposed method on homogeneous graph datasets. In addition, we follow previous work [3] to generate two different views of the homogeneous graph by removing edges and masking features. \n\n[3] Graph Contrastive Learning with Adaptive Augmentation. WWW 2021.\n\n> **Q6**. It would be better to add some recent works about the SHGL in the related work.\n\n**A6**. Thanks for your suggestion, we will add more recent related works in the final version.\n\n> **Q7.** The paper needs further proofreading. For example,\n\n​    1) In Eq. (17), what does the $\\hat{\\mathbf{q}}_{\\mathbf{y}_i}$ actually mean?\n\n​    2) The definitions of some symbols need to be further determined, such as $\\mathbf{I}$ in Definition 2.1.\n\n​    3) Some mistakes in Table 3.\n\n​    4) The caption of Table 7 should be fixed.\n\n**A7.** 1) $\\hat{\\mathbf{q}}_{\\mathbf{y}_i}$ indicates the cluster representation whose label equals to  $\\mathbf{y}_i$.\n\n​       2) $\\mathbf{I}$ indicates the identity matrix.\n\n​       3)-4) We will fix these mistakes in the final version.", "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": "gOLTBIEBK6", "reviewer": "Reviewer_NZZJ", "summary": "This paper proposes a theory-backed method for Self-Supervised Heterogeneous Graph Learning (SHGL) based on spectral clustering and incorporates rank constraint and node/cluster consistency regularizers to generate better embeddings. In specific, the authors start by showing that existing algorithms divide the representations into a certain number of clusters that are much larger than the number of real classes. Then, an objective function with rank constraint is proposed to reduce the noise of message-passing and consistency terms are employed to improve downstream task performance. Experiments on the real datasets show that the proposed method outperforms other baselines.", "questions": "1.\tIn Line 172, whose independence are we referring to? Why $H^T H=I$ is equivalent to statistical independence?\n2.\tIn practice, is it always the case that number of clusters equal to $c$ will give the optimal results?\n3.\tHow do we reach the inequality in (53) and (54)? Does the term in (55) correspond to the loss function in (17)?", "limitations": "The authors are encouraged to discuss the limitations in the main paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe paper analyzes the issue of the exiting methods that are based on meta-path-based graph or the adaptive graph structure theoretically. Furthermore, a rank and consistency constrained approach is proposed to tackle know issues of SHGL and it is shown to have less complexity theoretically.\n2.\tExperimental results show the superiority of the proposed method consistently over a variety of datasets.", "weaknesses": "1.\tNotations are not always clearly defined. For example, what are the dimensions of the mapping $g_{\\phi}$ and $p_{\\phi}$?\n2.\tThe derivation of the first loss term is not clear to me. Why is there an entropy constraint term in (13)? How do we translate Eq. (8) to Eq. (13) and what is the correspondence of the terms? Line 183 states that ‘fitting eigenvectors F by (13)’, but it seems that F does not appear (13). Or is it that (13) is only for solving the last term in (8)? Clarity can be further improved upon the objective function, especially the term $\\cal{L}_{sp}$.\n3.\tWhy is $Y$ a probability matrix? Is there any guarantee on that? Only orthogonality is proved for the matrix. Do we need a simplex constraint on the columns of $Y$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments on our theoretical and experimental results. We are so encouraged and will try our best to address the concerns one by one. \n\n> **Q1.** Some undefined notations, e.g., the dimensions of $g_\\phi$ and $p_\\varphi$.\n\n**A1**. We employ $g_{\\phi}\\in\\mathbb{R}^{f\\times d_1}$ and $f_\\theta\\in\\mathbb{R}^{f\\times d_1}$ to derive semantic and heterogeneous representations, where $f$ and $d_1$ are the dimensions of node features and representations, respectively. We then employ projection heads $p_{\\varphi}\\in\\mathbb{R}^{d_1\\times c}$ and $q_\\gamma\\in\\mathbb{R}^{d_1\\times d_2}$ to map representations, where $c$ and $d_2$ are mapped dimensions. We summarized the settings of the above notations in Table 3 in the uploaded PDF file.\n\n> **Q2.** Unclear derivation of the first loss. Why an entropy constraint in (13)? How do we translate (8) to (13) and what is the correspondence terms? Or is (13) only for solving the last term in (8)? Clarity can be further improved upon $\\mathcal{L}_{sp}$.\n\n**A2**. The second term (i.e., the entropy constraint) in Eq. (13) is used to maximize the entropy of $\\mathbf{Y}$ (the entropy is maximum when nodes are evenly assigned in different clusters), thereby preventing most nodes from being assigned to the same cluster.\n\nThe first term in Eq. (13) is only for solving the last term in Eq. (8). Specifically, as stated in lines 153-157, Eq. (8) is solved by the alternating optimization, i.e., fix $\\mathbf{S}$ then optimize $\\mathbf{F}$, and fix $\\mathbf{F}$ then optimize $\\mathbf{S}$. When fixing $\\mathbf{F}$, Eq. (8) only remains the first two terms to optimize $\\mathbf{S}$ (the last term in Eq. (8) is fixed), thus we can obtain the closed-form solution of $\\mathbf{S}$ with Eq. (10). When fixing $\\mathbf{S}$, Eq. (8) only remains the last term to optimize $\\mathbf{F}$ (the first two terms in Eq. (8) are fixed), which requires cubic time complexity due to the eigendecomposition. Hence, we replace it with neural networks (i.e., $p_\\varphi$ and orthogonal layer) and the spectral loss to reduce the time complexity.\n\nTherefore, $\\mathcal{L}_{sp}$ in Eq. (13) consists of two parts, i.e., the first term optimizes $\\mathbf{Y}$ to approximate $\\mathbf{F}$ to solve the last term of Eq. (8), and the second term assigns nodes evenly into different clusters. \n\n> **Q3.** Why is $\\mathbf{Y}$ a probability matrix? Any guarantee on that? Do we need a simplex constraint on $\\mathbf{Y}$?\n\n**A3**. In the submission, we called $\\mathbf{Y}$ as the probability matrix, because $\\mathbf{Y}$ indicates the prediction to assign nodes to different clusters, and the larger the value $\\mathbf{y}_{ij}$, the greater the probability of node $v_i$ to be assigned to the $j$-th cluster. There is no other constraint (e.g., the simplex constraint) on $\\mathbf{Y}$ except the orthogonality and spectral loss. Indeed, $\\mathbf{Y}$ is not a typical probability matrix, and we will rename it as the cluster assignment matrix in the final version to avoid confusion.\n\nIn the rebuttal, we further conducted experiments to add the simplex constraint on $\\mathbf{Y}$, and reported the results in Table 4 in the uploaded PDF file. In Table 4, the method with the simplex constraint obtains inferior results than the method without. This is reasonable because adding a simplex constraint to $\\mathbf{Y}$ may hinder its approximation to $\\mathbf{F}$, affecting the quality of the affinity matrix.  \n\n> **Q4.** In Line 172, whose independence is referring to? Why $\\mathbf{H}^T\\mathbf{H}=\\mathbf{I}$ is equals to statistical independence?\n\n**A4.** The independence refers to the independence among different representation dimensions. Specifically, $\\mathbf{H}^T\\mathbf{H}\\in \\mathbb{R}^{d_1\\times d_1}$ calculates the correlation among different dimensions of $\\mathbf{H}$, where $d_1$ is the dimension of $\\mathbf{H}$. After that, the constraint $\\mathbf{H}^T\\mathbf{H}= \\mathbf{I}$ enforces the off-diagonal elements of $\\mathbf{H}^T\\mathbf{H}$ to 0, thus minimizing the correlation among different dimensions of $\\mathbf{H}$ to achieve the statistical independence.\n\n> **Q5.** Is $c$ clusters always yield optimal results?\n\n**A5.** To verify it, we changed the number of clusters and reported the results in Figure 1 in the uploaded PDF file. Obviously, our method obtains the best results when the number of clusters equals $c$ and decreases as the number of clusters increases. This is reasonable because if the number of clusters is larger than $c$, the nodes within the same class may be divided into different clusters. Moreover, if the number of clusters is smaller than $c$, the nodes from different classes may be divided into the same cluster. \n> **Q6.** How do we reach the inequality in (53) and (54)? Does the term in (55) correspond to the loss function in (17)?\n\n**A6.** We can reach (53) and (54) by proving the following inequality: $$a^2b+(1-a)^2c\\ge\\frac{bc}{b+c}, $$where $0\\le a\\le1$, and $0\\le b,c$. To prove it, we construct $f(a) = a^2b+(1-a)^2c-\\frac{bc}{b+c}$. We then take the derivative of $f(a)$, i.e., $$f'(a)=2ab-2c+2ac.$$ Then we let $f'(a)=0$, and have $a=\\frac{c}{b+c}$. We have $$f(\\frac{c}{b+c})=\\frac{c^2b}{(b+c)^2}+\\frac{b^2c}{(b+c)^2}-\\frac{bc}{b+c}=0.$$ In addition, we take the second-order derivative of $f(a)$ and obtain $$f''(a)=2(b+c)\\ge0.$$\n\nTherefore, $f(a)$ is decreasing when $a<\\frac{c}{b+c}$ and increasing  when $a>\\frac{c}{b+c}$, and reaches its minimum 0 at $\\frac{c}{b+c}$. Hence, $f(a)\\ge0$ always holds for $0\\le a\\le1$, thus proving the above inequality. We can reach the inequality in (53) by replacing $a$, $b$, and $c$ with $P_0$, $\\sigma_0^2$, and $\\sigma_j^2$, respectively. Similarly, we can also reach the inequality in (54). In addition, the term in (55) corresponds to the loss function in Eq. (17).\n> **Q7.** Discuss limitations in the main paper.\n\n**A7.** Thanks for the suggestion. We discussed limitations in Appendix F, and we will move them to the main paper in the final version.", "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": "RE68KHDAyh", "reviewer": "Reviewer_v7xk", "summary": "This work deals with the problem of self-supervised representation learning in heterogeneous graphs. First, a spectral-clustering based objective is presented to unify the objectives of existing methods. Second, a novel self-supervised method is proposed that tries to capture both the cluster information and node-level information in the learnt representation. Experiments show the effectiveness of the proposed method over existing methods.", "questions": "Please refer to the questions and comments in Weaknesses section.", "limitations": "Limitations and impacts are adequately discussed in the Appendix.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The proposed method is novel and follows a principled design.\n2. Presented theoretical analysis is helpful in deeper understanding of existing and proposed method.\n3. Experiemental section is comprehensive with adequate baselines, datasets, and ablations.", "weaknesses": "1. Presented theorems are often unclear or imprecise. For example\n\n   (a) In Theorem 2.6, authors use the term model complexity abruptly without any definition or reference. I could not understand the relation between the infimum and supremum of model complexity with generalization ability (which also needs to be rigorously defined).\n\n   (b) In Theorem 2.2, what exactly are the previous meta-path-based and adaptive-graph-based SHGL method mentioned in the theorem statement? What is the expression for the regularization term for the corresponding previous methods?\n\n   (c) There does not seem to be a clear delineation between what already exists in the literature and what is the new contribution of the paper. E.g., does Theorem 2.3 directly follow from existing results in the literature, or does this require custom analysis?\n\n   (d) Theorem 2.5 is not precise enough. When referring to \"proposed method\", it would be more precise to refer to specific objective function or algorithm block. Also \"equivalent to performing spectral clustering based on the affinity matrix ....\". Authors are recommended to replace the language description with precise objective function.\n\n\n\n2. The writing is often unclear and could be greatly improved. Several terminologies (which might not be standard in the literature) are never explained/defined. For example:\n\n   (a) Section 1 Line 42 \".. it is feasible to analyse ..\", it is not clear what exactly is feasible to analyse (although after Section 2.1, it can be understood).\n\n   (b) In abstract and introduction, it is not clear what is invariant information is\n\n   (c) Sentence in line 216-218 is unclear.\n\n   (d) How does H^T H = I imply statistical independence?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments on the novelty, theoretical analysis, and experimental results of our method. We are so encouraged and will try our best to address the concerns one by one.\n\n> **Q1.** Presented theorems are often unclear or imprecise. For example,\n\n> **Q1-a**. In Theorem 2.6, no definition or reference of the model complexity. Unclear relation between the infimum and supremum of model complexity with generalization ability.\n\n**A1-a**. Due to the space limitations, in the submission, we followed previous works [1-2] and gave Definition C.5 of the model complexity in lines 686-691 in Appendix C.4. In the rebuttal, we further followed previous works [1-2] to define the generalization error $E$ of a model based on the model complexity, i.e.,\n\n**Definition 1**. For any $\\delta \\in [0, 1]$, with probability at least $1-\\delta$,  the generalization error $E$ of a model follows the inequality, i.e., $$\nE \\le \\frac{1}{n} \\sum_{i=1}^{n} \\ell(f(x_i), y_{i})+\\sqrt{\\frac{C}{n}}+\\mathcal{O}(\\sqrt{\\frac{\\log (1 / \\delta)}{n}}),$$\nwhere $(x_i, y_i)$ is a pair of labeled data, $f$ is the model, $l$ is the loss function, $n$ is the number of labeled data, $C$ is the model complexity measure. Based on Theorem 2.6 and the Definition above, we can obtain that the proposed method obtains a lower model complexity boundary, thus achieving a lower generalization error and higher generalization ability boundary than previous SHGL methods. We will move Definition C.5 and add the above Definition 1 to the main paper in the final version.\n\n[1] Representation Based Complexity Measures for Predicting Generalization in Deep Learning. NeurIPS 2020.\n\n[2] Methods and Analysis of The First Competition in Predicting Generalization of Deep Learning. NeurIPS 2020.\n\n> **Q1-b.** In Theorem 2.2, what exactly are the meta-path-based and adaptive-graph-based SHGL methods, and their regularization terms?\n\n**A1-b.** In Theorem 2.2, the meta-path-based SHGL methods indicate the works that utilize meta-paths to build edges among nodes. Almost all SHGL comparison methods in the paper belong to this group, such as HGMAE, CPIM, HGCML, HeCo, HDMI, etc. We gave their regularization term in Appendix C.1 in Eq. (28). The adaptive-graph-based SHGL methods indicate the works that utilize the adaptive graph structure to build edges among nodes. Only the latest comparison method (i.e., HERO) belongs to this group. We gave the regularization term in Appendix C.1 in Eq. (35). We will clarify two group's methods and regularization terms in the main paper in the final version.\n> **Q1-c**. Clarify new contributions of the paper. E.g., does Theorem 2.3 require custom analysis?\n\n**A1-c**. Theorem 2.3 connects the traditional graph-cut algorithm with existing SHGL methods, which has never been done in the existing literature and requires custom analysis.  \n\nThe new contributions of the paper can be summarized as:\n\n1) Motivation: We first attempt to revisit existing SHGL methods from the spectral clustering perspective in a unified manner.\n\n2) Theory: This paper builds theoretically connections between previous SHGL methods and the spectral clustering as well as the graph-cut algorithm, which have never been analyzed in existing literature.  \n\n3) Method: This paper proposes for the first time to adaptively learn a rank-constrained affinity matrix and introduce a dual consistency constraint to alleviate the issues in previous methods.\n\n> **Q1-d.** Theorem 2.5 is not precise enough.\n\n**A1-d.** Thanks for your suggestion, we will reformulate Theorem 2.5 in the final version as follows,\n\n**Theorem 2.5.** Optimizing the spectral loss $L_{sp}$ leads to performing the spectral clustering based on the affinity matrix $\\mathbf{S}$ and conducting RatioCut ($V_1,\\ldots, V_c$) algorithm to divide the learned representations into $c$ partitions, i.e.,\n$$\n\\min L_{sp} \\Rightarrow \\min \\operatorname{Tr} (\\mathbf{Y}^T\\mathbf{L}_S\\mathbf{Y}) \\Rightarrow \\min \\operatorname{RatioCut}(V_1,\\ldots,V_c),\n$$\nwhere $\\mathbf{Y}$ is the cluster assignment matrix, $\\mathbf{L}_S$ is the Laplacian matrix of the affinity matrix $\\mathbf{S}$, $\\operatorname{Tr}(\\cdot)$ indicates the matrix trace, and $c$ is the number of classes.\n\n> **Q2.** The writing is often unclear and could be greatly improved. \n\n(a). Section 1 Line 42, it is not clear what exactly is feasible to analyse (although after Section 2.1, it can be understood).\n\n(b). In the abstract and introduction, it is not clear what the invariant information is. \n\n(c). Sentence in line 216-218 is unclear.\n\n(d). How does $\\mathbf{H}^T\\mathbf{H}= \\mathbf{I}$ imply statistical independence?\n\n**A2.** (a) We will modify it as \"it is feasible to analyze previous SHGL methods from a clustering perspective thanks to their close connection to clustering techniques ...\". Actually, we have mentioned this connection in lines 24-33.\n\n(b) Although node representations collect information from nodes within the same type, and heterogeneous representations collect information from nodes of different types, they both contain the same feature of the node itself, which we call the invariant information.\n\n(c) We will modify it as \"In addition, according to Theorem 2.2, previous SHGL methods actually perform spectral clustering to learn node representations. However, previous SHGL methods fail to utilize the cluster-level information outputted by the spectral clustering, thus weakening the downstream task performance.\"\n\n(d) The independence refers to the independence among different representation dimensions. Specifically, $\\mathbf{H}^T\\mathbf{H} \\in \\mathbb{R}^{d_1 \\times d_1}$ calculates the correlation among different dimensions of $\\mathbf{H}$, where $d_1$ is the dimension of $\\mathbf{H}$. After that, the constraint $\\mathbf{H}^T\\mathbf{H}= \\mathbf{I}$ enforces the off-diagonal elements of $\\mathbf{H}^T\\mathbf{H}$ to 0, thus minimizing the correlation among different dimensions of $\\mathbf{H}$ to achieve the statistical independence.", "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": "gzsPHGhC3F", "reviewer": "Reviewer_oBdx", "summary": "The paper proposes a new framework that revisits SHGL from a spectral clustering perspective, incorporating rank and dual consistency constraints. This approach uses a rank-constrained spectral clustering method to refine the affinity matrix and remove noise, while also integrating node-level and cluster-level consistency constraints to better capture and use invariant and clustering information. Theoretical analysis and experimental results show that this new method significantly improves performance in downstream tasks compared to existing methods.", "questions": "Please find questions in the weaknesses above.", "limitations": "This paper does not mention the limitations of this work or the potential negative societal impacts.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper provides a theoretical investigation of previous SHGL methods from the perspective of spectral clustering.\n2. This paper proposes a new framework to capture the cluster-level graph invariant representations.\n3. Experiments demonstrate the effectiveness of the proposed methods.", "weaknesses": "Unfortunately, this paper is not easy to follow due to the missing parts in terms of motivation and logic.\n\n1. In the introduction part, the authors mention three challenges abruptly from Lines 44 to 48. However, it is unclear why they are challenging to address. For example, why it is difficult to understand previous SHGL methods from the clustering perspective?  It is also unclear the logical relationships between the three challenges.\n\n2. In Section 2, the authors introduce some notations about the heterogeneous graph. However, it is unclear what is the objective of the problem.\n\n3. In Section 2.1, it is unclear why authors need to bridge the gap between SHGL methods and graph-cut algorithm, and what is its benefits.\n\n4.  In Section 2.2, it is unclear why the rank constraint can mitigate noisy connections.\n\n5. When reading Section 2.2, the reviewer gets lost in the lemma and equation details. It is better if the authors can highlight the contributions and leave all technical derivations to the appendix.\n\n6. The logical relationship between Sections 2.2 and 2.3 is unclear. Why both the low-rank constraints and dual consistency constraints should be imposed, and what is the relationship between these two constraints?\n\n7.  In the experiments, it is unclear why two homogenous graph datasets were used for performance evaluation, given the objective of this paper is for heterogeneous graph learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive comments on the novelty, theoretical analysis, and experimental results of our method. We are so encouraged and will try our best to address the concerns one by one.\n\n> **Q1.** Unclear why three challenges are challenging to address and the logical relationships between them.\n\n**A1.** Since previous SHGL methods are close to clustering techniques, as stated in lines 30-33, and suffer from two issues (i.e., noisy connections and neglect of cluster-level information), as stated in lines 34-41, we have challenges as follows.\n\n(i) To formally understand previous methods from clustering perspective. This is challenging because no existing literature formally connects self-supervised graph learning with spectral clustering. This requires us to derive the whole process from scratch.\n\n(ii) To learn an adaptive graph structure to avoid inter-class noise. The challenge is hard to solve because although some graph structure learning works [1-2] try to optimize graph structures, they may have noisy connections due to the lack of theoretical guarantees.\n\n(iii) To effectively incorporate cluster-level information to boost downstream tasks. This is difficult as existing works often divide nodes within the same class into different clusters, resulting in sub-optimal cluster-level information that cannot be used in an effective way.\n\nRelationships: Challenge (i) is the theoretical basis of the whole paper and points out the direction for solving the following two challenges. The latter two challenges build on each other under the theory framework of challenge (i). Specifically, challenge (ii) mitigates noise and outputs high-quality cluster-level information for challenge (iii), while challenge (iii) aligns intra-class representations, thus aiding challenge (ii).\n\n[1] Towards Unsupervised Deep Graph Structure Learning. WWW 2022.\n\n[2] Heterogeneous Graph Structure Learning for Graph Neural Networks. AAAI 2021.\n\n> **Q2.** In Section 2, unclear the objective of the problem. \n\n**A2.** The goal is to learn a model receiving diverse types of nodes and edges in the heterogeneous graph as input, and output low-dimensional representations for downstream tasks. We will add it in the final version.\n\n> **Q3.** In Section 2.1, unclear why to bridge the gap between SHGL methods and graph-cut algorithm and what is its benefits.\n\n**A3.** Theorem 2.3 bridges the gap between them to further point out the issues in previous SHGL methods. That is, previous SHGL methods cut the learned representations into $d$ clusters, which is much larger than the number of classes $c$. Therefore, nodes within the same class may be divided into different clusters, thus the learned representations cannot be clustered well.  \n\nBenefits: Theorem 2.3 gives the theoretical motivation of Section 2.2 and provides a direction for improving previous SHGL methods, i.e., adding low-rank constraints to divide the learned representation into $c$ clusters instead of $d$ in previous methods.\n\n> **Q4.** Unclear why the rank constraint can mitigate noisy connections.\n\n**A4.** The ideal noise-free affinity matrix is to only contain connections within the same class and have no noisy connections among different classes. That is, the ideal affinity matrix contains exactly $c$ (i.e., the number of classes) connected components. Based on Lemma 2.4, if the rank of $\\mathbf{L}_\\mathbf{S}$ equals $n-c$, then the affinity matrix $\\mathbf{S}$ contains exactly $c$ connected components to achieve the ideal case and mitigate noisy connections.\n\n> **Q5.** In Section 2.2, the reviewer gets lost in lemma and equation details. It is better to highlight the contributions and leave all technical derivations to the appendix.\n\n**A5.** Section 2.2 is designed to mitigate noise with the rank constraint, and we highlight it as follows. First, we propose to learn an adaptive graph structure via Eq. (5). After that, Lemma 2.4 explains how we add the rank constraint to Eq. (5) to avoid noise. Then we rewrite the rank constraint to spectral clustering by Eq. (6)-Eq. (8) as the rank constraint is not easy to tackle. Finally, we solve Eq. (8) by alternating optimization, i.e., fix eigenvectors $\\mathbf{F}$ to obtain the closed-form solution of the affinity matrix $\\mathbf{S}$ by Eq. (9)-Eq. (10), while fixing the affinity matrix $\\mathbf{S}$ to obtain the optimized eigenvectors $\\mathbf{F}$. To avoid the high time complexity of eignedecomposition, we replace it with Eq. (11)-Eq. (13) to efficiently approximate $\\mathbf{F}$ with $\\mathbf{Y}$. We will leave most derivations in the appendix in the final version.\n\n> **Q6.** The logical relationship between Sections 2.2 and 2.3 is unclear. Why impose both low-rank and dual consistency constraints, and what is the relationship between them?\n\n**A6.** Without the low-rank constraint, our framework would be affected by noisy connections. Without the dual consistency constraint, our framework would fail to consider the cluster-level information, thereby weakening downstream tasks. Hence, it is crucial for our method to impose both constraints.\n\nRelationships: The rank constraint in Section 2.2 and the dual consistency constraint in Section 2.3 actually benefit from each other. Specifically, the rank-constrained spectral clustering provides high-quality cluster-level information for the dual consistency constraint. Moreover, the dual consistency constraint encourages the representations within the same class to align with each other to help the rank-constrained spectral clustering.\n\n> **Q7.** Unclear why homogeneous graph datasets were used for evaluation.\n\n**A7.** We use both heterogeneous and homogeneous datasets to verify the effectiveness of our method on different types of graphs.\n\n> **Q8.** There is no discussion of limitations or potential negative societal impacts.\n\n**A8.** We discussed limitations and potential negative societal impacts in Appendix F, and we will move them to the main paper in the final version.", "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 would like to thank all the reviewers for their insightful and constructive comments. Due to space limitations in the rebuttal, we listed tables and figures in the uploaded PDF file. All modifications will be found in the final version. Our key responses are summarized as follows:

**> Clarification of unclear points.**

As Reviewer NZZJ suggested, we provided more details to clarify some notations. For example, the dimensions of the encoders $g_\phi$, $f_\theta$, and projection heads $p_\varphi$, $q_\gamma$. Moreover, we provided more explanation to clarify the objective function $\mathcal{L}_{sp}$. In addition, we renamed $\mathbf{Y}$ as the cluster assignment matrix to avoid confusion. Finally, we provided more explanations to clarify the statistical independence.

As Reviewer v7xk suggested, we provided more explanation to clarify previous SHGL methods in Theorem 2.2, and listed their corresponding expressions for the regularization term. Moreover, we highlighted the new contributions of the paper, compared to previous literature. In addition, we provided explanation and modified the sentences in abstract and introduction for a clear expression. 

As Reviewer oBdx suggested, we explained three challenges and the logical relationships between them. Moreover, we clarified the objective of the problem, the reason for bridging the gap between SHGL methods and graph-cut algorithm, and its benefits. In addition, we explained why rank constraints can mitigate noisy connections and the logical relationship between Sections 2.2 and 2.3. Finally, we explained why homogeneous graph datasets were used for performance evaluation.

**> Additional theoretical details.**

As Reviewer NZZJ suggested, we provided the details to reach the inequality in (53) and (54).

As Reviewer v7xk suggested, we will move the definition of the model complexity in the appendix to the main paper. Moreover, we provided the definition of the relationship between model complexity and generalization ability. In addition, we reformulated language description with a precise objective function to achieve precise Theorem 2.5.

**> Additional experimental results.**

As Reviewer LzB2 suggested, we conducted experiments to replace the proposed node-level consistency constraint with the InfoNCE loss. Moreover, we conducted experiments to replace the affinity matrix with the simple cosine similarity and self-attention mechanism.

As Reviewer NZZJ suggested, we conducted experiments to add a simplex constraint on the columns of $\mathbf{Y}$. Moreover, we conducted experiments to change the number of clusters in the proposed method.

**> Other responses.**

As Reviewer LzB2 suggested, we provided a real example to better illustrate the noise in meta-path-based graphs and adaptive graph structures. Moreover, we provided more details about the specific processes for different downstream tasks and the implementation on the homogeneous graph.

**> Summary.**

We thank all the reviewers again for the detailed and constructive review. It seems that almost all the reviewers have agreed with the novelty and contributions of the proposed method, and that most of the concerns are raised to part of the unclear expressions, and experiments. We hope our clarification, additional theoretical details, and additional experimental results in the rebuttal could address all of your concerns. Please let us know if you have any  questions or concerns.

Meta-review: This work introduces a novel loss function for graph embedding, drawing on insights from spectral clustering, along with dual consistency regularizations and orthogonality constraints.

The reviewers collectively appreciated the innovative perspective of the paper, particularly its connection to spectral clustering. They also commended the theoretical justification provided for the proposed loss function. Several reviewers noted that the experimental section was comprehensive, offering sufficient baseline comparisons.

However, the primary concerns raised were related to presentation. The reviewers pointed out issues with the clarity of notation and the use of certain terminologies, such as distinguishing between statistical independence and uncorrelatedness, and the definitions of terms like "probability matrix" and "complexity measure." These concepts were either not carefully defined or misused. In their rebuttal, the authors thoroughly addressed these concerns and acknowledged the need for improvements in writing and presentation.

Given the unanimous positive recommendations from the reviewers and the fact that the authors have the opportunity to address the clarity and presentation issues before publication, I recommend accepting this work.
Decision: Accept (poster)