Weakly Supervised Graph Clustering
Authors: Tian Bian
Tingyang Xu
Yu Rong
Wenbing Huang
Xi Xiao
Peilin Zhao
Junzhou Huang
Hong Cheng
Venue: ICLR 2022 Submitted (2022)

Abstract: Graph Clustering, which clusters the nodes of a graph given its collection of node features and edge connections in an unsupervised manner, has long been researched in graph learning and is essential in certain applications. While this task is common, more complex cases arise in practice—can we cluster nodes better with some graph-level side information or in a weakly supervised manner as, for example, identifying potential fraud users in a social network given additional labels of fraud communities. This triggers an interesting problem which we define as Weakly Supervised Graph Clustering (WSGC). In this paper, we firstly discuss the various possible settings of WSGC, formally. Upon such discussion, we investigate a particular task of weakly supervised graph clustering by making use of the graph labels and node features, with the assistance of a hierarchical graph that further characterizes the connections between different graphs. To address this task, we propose Gaussian Mixture Graph Convolutional Network (GMGCN), a simple yet effective framework for learning node representations under the supervision of graph labels guided by a proposed consensus loss and then inferring the category of each node via a Gaussian Mixture Layer (GML). Extensive experiments are conducted to test the rationality of the formulation of weakly supervised graph clustering. The experimental results show that, with the assistance of graph labels, the weakly supervised graph clustering method has a great improvement over the traditional graph clustering method.

the global label of the graph to Under review as a conference paper at ICLR 2022
GRAPH CLUSTERING WITH THE WEAK SUPERVISION FROM GRAPH LABELS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Clustering, which clusters the nodes of graph given its collection of node features and edge connections in an unsupervised manner, has long been researched in graph learning and is essential in certain applications. While this task is common, more complex cases arise in practice-can we cluster nodes bet- ter with some graph-level side information in weakly supervised manner as, for example, identifying potential fraud users in a social network given additional labels of fraud communities. This triggers an interesting problem which we define as Weakly Supervised Graph Chustering (WSGC). In this paper, we firstly discuss the various possible settings of WSGC, formally. Upon such discussion, we in- vestigate particular task of weakly supervised graph clustering by making use of the graph labels and node features, with the assistance of hierarchical graph that further characterizes the connections between different graphs. To address this task, we propose Gaussian Mixture Graph Convolutional Network (GMGCN), a simple yet effective framework for learning node representations under the pervision of graph labels guided by proposed consensus loss and then inferring the category of each node via Gaussian Mixture Layer (GML). Extensive experi- ments are conducted to test the rationality of the formulation of weakly supervised graph clustering. The experimental results show that, with the assistance of graph labels, the weakly supervised graph clustering method has great improvement over the traditional graph clustering method.
INTRODUCTION
With the development of deep graph learning, graph clustering has achieved significant improve- ment in community detection (Jin al. 20019), text clustering (Aggarwal & Zhai 2012) and other applications (Yang al. 2010). Such applications all assume that only node/edge information and connections accessible to assist with graph clustering in an unsupervised manner. However, it is possible that more graph-level side information, such as graph labels, may also be accessible and helpful for clustering the nodes in graphs. Or namely, can help improve the effectiveness of graph clustering?
This problem is interesting and very common in the real world. For example, point cloud segmenta- tion, which could be re-considered as clustering of nodes in point cloud if we only know the objects contained in each point cloud but all the node labels the training process instead of predic- tions for nodes with known node labels that are solved by supervised graph learning methods (Ye) al., 20188] Li et al. 2019). Moreover, in social media. thinking of hot events that are widely dis- cussed in the form of graphs where users are involved as nodes and the mutual following relationship among users as edges,
interesting to think how to pick out the malicious users from the mass of users with the labels of these event topics such as the authenticity of each topic (Zhou & Zafarani 2018 Cao et al. 2018). Actually, this problem is more like graph clustering in a weakly supervised manner (Zhou] 2018), or named Weakly Supervised Graph Clustering (WSGC), where the avail- able training labels are much coarser- coarser-graines grained than the node labels we want to fit. Unlike traditional graph clustering (Girvan & Newman, 2002) which only conducts clustering based node features or graph structures, WSGC is better guaranteed by the given label information of graphs, which, we will demonstrate, closely influences the clustering results.

---

Under review as a conference paper at ICLR 2022
Note that WSGC is different from traditional weakly supervised learning problems. Generally, weakly supervised learning is considered to consist of three types of weak supervision problems: incomplete supervision, inaccurate supervision and inexact supervision (Zhoul 2018). WSGC is different from incomplete supervision where a subset of training nodes is given with labels and in- accurate supervision where the given node labels not always ground-truth, since WSGC does not contain any node labels for training. It is also different from inexact supervision, whose represen- tative method as Multiple-Instance Learning (MIL) (Carbonneau et al. 2018 adopts global labels of bags to identify the labels of local instances. Because MIL assumes that each instance is i.i.d. and there are no edge connections involved. As far as we know, there are no studies on WSGC even though WSGC is very useful to formulate some real-world problems. Therefore, it is interesting and important to study the WSGC as a new challenge and seek new solutions for it.
In this paper, we formally define Weakly Supervised Graph Clustering (WSGC), i.e. graph cluster- ing task by making use of graph labels, graph structure and node features. To address this particular task, we propose novel model based on Gaussian mixture model (GMM) and graph convolutional network (GCN) named as Gaussian Mixture Graph Convolutional Network (GMGCN), The pro- posed model includes Gaussian mixture layer (GML) and a new hierarchical GAT (hierGAT) to update the node and graph hidden representations, respectively. Specifically, we design a consen- sus loss that plays key role in improving node clustering with the assistant of graph labels in the training process. Finally, a graph clustering is carried out according to the parameters of GMI., The main contributions are follows:
We introduce a new problem, i.e. Weakly Supervised Graph Clustering (WSGC), which tries identify the nodes in graphs based on the labels of graphs, and we take a formal discussion of the variants of this problem to attract more research attention on this problem. 2. New solution: We propose an effective model called GMGCN based on GMM and GCN to solve WSGC. To the best of our knowledge, this is the first work to achieve graph clustering in graph structure by integrating GMM into GCN. 3. New loss: We propose a consensus loss function to boost the model training through the principle of "same attraction, opposite repulsion". Experiments validate the effectiveness of this consensus loss.
1. New problem:
We validate the significant improvement of WSGC over traditional clustering methods various synthetic and real-world datasets. Compared to the best performing baseline method, GMGCN improves Normalized Mutual Information (NMI) by average of 13% on 5 synthetic datasets, by more than 13% on PHEME social media datasets, and improves mean intersection-over-unee (mloU) by more than 18% on point cloud segmentation datasets.
2 RELATED WORKS
Graph Learning. Recently, there has been an increasing interest in the graph learning domain. Among all the existing works, GCN is one of the most effective convolution models. A typical GCN model is the message passing neural network (MPNN) proposed by Gilmer er al. (Gilmer et al., 2017) which re- re-generalizes several neural network and graph convolutional network approaches as a general "message- paaagggg-pssng""" architecture. Many kinds of GCN (Bruna et al. 2014 Defferrard et al.) 2016 Kipf& & Welling 2017; Chang et al.) 2020) deliver different message propagation functions for GCN. Among them, Graph Attention Networks (GAT) (Veličković et al. 2017) first leverages learn- able self-attentional layers aggregate weighted neighbors' information. Besides these methods to obtain the appropriate node representation, pooling strategies are proposed to integrate information over the node representations (Wu et al. 2020), such as max/min pooling (Defferrard et al., (016)) SortPooling (Zhang et al. 2018), and so on. In addition, Lin et al. (Lin et 2017) propose learn- able attentive pooling for weighted averaging of node representations. Despite extensive research on node-level and graph-level graph learning tasks, few studies have been conducted on WSGC.
Graph Clustering, Graph clustering is a fundamental data analysis task that aims to group similar nodes into the same category. Many real-world applications are cast as graph clustering (Shi & Ma-
NM is a normalization of the Mutual Information score scale the clustering results between (no mutual information) and (perfect correlation).
'loU is commonly used metric in semantic segmentation measures similarity between finite sample sets, and is defined the size of the intersection divided by the size of the union of the sample sets.
2

---

Under review as a conference paper at ICLR 2022
lik 2000 Hastings 2006). The major strategy of graph clustering is to perform traditional clustering algorithms such as K -mmans (Jain 2010) or GMM (McLachlan & Basford 1988) on the node fea-
tures. With the great achievements of deep learning, more graph clustering studies have resorted to graph learning to learn embedding that captures both node features and structural relationships (Wu et al. 2020). Researchers employ the stacked sparse autoencoder (Tian et al.) 2014), the variational autoencoder (Kipf & Welling, 2016), or the combination of both autoencoder and GCN (Bo et al., 2020) to obtain graph representations for clustering. Nevertheless, these graph clustering methods do not perform better than WSGC methods due to the lack of attention to graph labels.
Multiple-Instance Learning. Another task that has similar definition WSGC is Multiple- Instance Learning (MIL), MIL is a variant of inductive machine learning, where each learning ex- ample consists of a bag of instances instead of single feature vector (Foulds Frank (010)). When obtaining local instances annotations is costly not possible, but global labels for bags are avail- able, MIL is utilized to train classifiers using weakly labeled data. has received considerable amount of attention due to its applicability to real-world problems (Andrews al. 2002a Cheply- gina et al. 2019). Although MIL learns a classifier from the labels of bags to classify instance, ignore structural information between instances and are therefore not suitable for WSGC.
Gaussian Mixture Model. As a core part of the proposed GMGCN model, GMM is a paramet- ric probability density function for a weighted
of Gaussian component densities (McLach- lan & Basford 1988). It is commonly used to find underlying clusters in data samples (Bishop) estimated using the iterative Expeetation-Maximmzatiio (EM) (Moon] 1996) algorithm from training data. In this paper, we integrate the GMM into GCN to establish solution for WSGC and update the GMM parameters using stochastic gradient descent.
2006). Generally, the GMM parameters
Point Cloud Semantic Segmentation. Semantic segmentation of 3D point clouds has attracted more researchers' attentions due to the developments of 3D scanners, such as Light Detection and motion (SFM) techniques, etc. To operate directly on these un- structured point clouds, PointNet (Qi al., (017aa) proposed subdivide the input points into grid of blocks and process each such block individually, but limited neighborhood context of each point is taken into consideration. To overcome this drawback, many approaches (Engelmann al.] 2017 Ye et al. 2018 Qi et al. (2017)) are built upon PointNet and better capture local spatial struc- tures as well as long dependency context. Recently, some latest works (Qi et al. 2017c Landrieu & Simonovsky 2018 Wang et al. 2019) re-consider semantic segmentation of unstructured 3D point clouds as predictions for nodes on graph data and incorporate contextual information and topological information on top of 3D points. However, these supervised graph learning methods not suitable for weakly supervised point cloud semantic segmentation datasets if the point labels are unknown.
Ranging (LIDAR), structure-from -rote--mooomoooionn
NOTATIONS AND PROBLEM STATEMENT
3.1 NOTATIONS
We denote a set of graph instances as G = (()) refers to the n--hh graph instance and n()) E (0, I,..., Cgroph - 13 is the corresponding graph label of Cgroph different categories. We denote by g(n) (V(m), (V(m),g(n) the n-th graph instance of
()()))} with N graphs, where
Mr. E IR M. xd the feature matrix of nodes y/()) where d denotes the number of dimensions of node original features, and by A (n) {0, 13 M,, M, the adjacency matrix which associate edge (o."), ((") with A/3). We denote by (2(m) ..... 2 Mr E {0. 1.... Cnode 1} the potential labels of nodes v/(*) where Cnode is the expected number of node categories. In addition, we denote by A kier E (0, 10 the adjacency matrix of the links among graphs if the graphs in G contain interconnections.
size Mn with nodes v!" E E and edges (v. 205 (())) E g(n), by (()) = {=]
(n)
x
3.2 PROBLEM STATEMENT
The Weakly Supervised Graph Clustering (WSGC) problem is defined as: Given a set of graph-label pairs G and node features X, how to infer the label of the i-th node in the n-th graph, 2("), where n E {1....,]] N} and E {l...., M, Under the definition of WSGC, there are some different cases that could be extended from the problem new tasks.
3

---

Under review as a conference paper at ICLR 2022
Case (Infer Original Nodes) Given the whole G and X training data, how to infer all the node labels 2/ the g(m)s? s?
Case 2 (Infer New Nodes) Given the portion of nodes v(n) = {ei ..... U
(m) M
- in each ((m)
as training data, how to infer the labels of the rest of s nodes { (MM--oe -
(2) Ma
} in the gin)s?
Case 3 (Infer New Graphs) Given the portion of graphs Gtrain (( , )....... (GIN- ((N-S) .y {(N- as training data, how to infer the node labels (N- SS 1,..,,, in the rest of S graphs, {G C(.,,
Case 4 (With/Without Hierarchical Graph) Given the interconnections among graphs as Abters how to infer the node labels? And if there are interconnections, how to infer the node labels (i.e. A hiir I)?
4 PROPOSED METHOD
In this section, first introduce the preliminaries related to the proposed model, then we discuss details of the proposed method.
4.1 PRELIMINARIES
Graph Attention Networks. Graph Attention Networks (GAT) (eličković et al. 2017) has been widely adopted in the field of graph convolution due to the learnable attentions neighbors during the message passing process. A multi-head GAT Convolutional layer (GATConv) is formulated as:
K h4 || aaa
Oz,
Σ JEN()
a Oz,),
where hú and J. refer the hidden feature representation for the next layer and the current hidden feature vector of node in the graph, respectively. || refers to concatenation operation for K-head attention, and (-) refers to the nonlinear activation function. is the weight matrix and NN the set of neighbors of node i. at is the attention coefficient computed by the k-th attention mechanism as follows:
exp(LealyRel..U (
O7,1))
O.. ΣlEN(OU() exp(LeakReeLU(T') [O || Oz))
where attention mechanism is single-layer feedforward neural network parametrized by a weight vector a and applying the LeakyReL.U nonlinearity.
Graph Attentive Pooling. Lin al. (Lin et al.) 2017) employ self-attentive mechanism to learn the importance of each node and then transform variable number of node representations into fixed-length graph representation:
h in) = Attn (H)) softmax O @ (T) )))
(3)
where ④11 and .2 refer to trainable parameters. The unified graph representation of the n-th graph (n)
hg is obtained by multiplying the node attention scores with (n).
4.2 OVERALL FRAMEWORK
Fig. [ gives an overall framework the proposed method to infer the categories of the nodes in the graphs. It consists of five processes: node-level modeling, node feature redistribution, graph instance modeling, hierarchical graph modeling and consensus loss calculation. The node-level modeling consists of 2-layer Multi-Head GAT and the graph instance modeling is accomplished by aggregating graph-level representations from the node-level GML via graph attentive pooling. In this section, will introduce the rest of the three key components of the proposed framework.
4

---

Under review as a conference paper at ICLR 2022
Node-level Moceling
Node Feature Red eribution
Graph Pasance Moceling
Herarenical Graph Modwing
2-ayer
Attentive Fooling
Consenous Loss
Hasanchical Graph
Crach
Cetribution
Craph Embaddingi
Herarchiccl Connections
Forward
hg
Ps
f1
Guide
b
Node Updating
Graph Updating
Consensus Distance
Figure 1: The overall framework of the proposed GMGCN, (a) Model forward propagation consists of five pro- cesses: node-level modeling. node feature redistribution, graph instance modeling, hierarchical graph modeling and consensus loss calculation. (b) During the backward propagation. the distances between graph represen- tations hg obtained via hierGAT and the mean vector μ of each Gaussian weight function will guide graph updating and further influence the node updating.
Gaussian Mixture Layer (GML). As the key component of the GMGCN, GML plays crucial
role the process of node feature redistribution. It is described as 74 Cyraph
Ee
Caraph we (h(h))
where w-)-) represents the Gaussian weight function follows:
w.(fi exp(
(Oamth - p)))),
2
where Te and Tee are learnable standard deviation vector and mean vector, respectively, and OCMe refers to the learning parameters.
Based on the idea of GMM, GML has the ability to effectively distinguish different types of nodes according to the input features. However, it could not resolve two major challenges of WSGC: the node-level modeling and the graph instance modeling that affects the final node inference. There- fore, we employ the node representations from the 2-layer GAT as inputs of GMI. The node repre- sentations provide local structural information of the nodes to GML. Meanwhile, the outputs N2 of
GML aggregated by attentive pooling (n) and further fed into hierarchical GAT.
Hierarchical GAT (hierGAT), As mentioned Case f the information of interconnections among graphs may infer the node labels. To model such hierarchical structure information, employ 3-layer hierGAT to update the feature representations in the hierarchical graph as Eq. (5)
H hierGAT((H)) 33 hier H' 9 + (1 (1-3)) H)
(5)
where E 1, refers to the layer number of the 3-layer hierGAT, lier refers to the hierarchical attention coefficients, and HO = Hy. which the hierarchical feature matrix that consists of the
feature representations of graphs, h)"), Each hicrarchical attention coefficient hier in a hier is oy caluculated Eq. 2h. We define the final output of the 3-layer hierGAT H² as Hy- There are no training parameters that causes the spatial transformation in Eq. (5) so that the node embeddings ('()) and graph embeddings H', are still the same hidden space. Note that, the hierGAT is reduced to version without using the hierarchical graph when B 0.
Consensus Loss. The core idea of consensus loss to make the graph representations with the same labels closer, and those with different labels farther away in the hidden space. Therefore, before computing the consensus loss, we first compute the similarity matrix S E R2 XCpraph of the graph representations, which obtained by the following steps:
First, we compute the distance between the graph representation T((n) obtained via hierGAT and the mean vector fhc of e-th Gaussian weight function follows:
dnc
flc ||2
5

---

Under review as a conference paper at ICLR 2022
Second, enhance the distance of the graph representations to the true vector on dne by:
(dne)enhance dne + ndyn))
where 5 is a discount hyperparameter, y(m) the true label of graph g(,), and day(n represents
the distance between the graph representation (h and the mean vector Myens: Then the similarity matrix S is formulated S Finally, the consensus loss is formulated as Leon = cross cross.entropu((..) entropu(S.y).
where D Denhance consists of (dre) enhaneee
Model training Guidance. As shown in Fig. bb), the consensus loss makes the graph representa- tion of each graph (e.g. hg) closer to the mean vector of the Gaussian function corresponding to its graph label (e.g. the yellow arrow), so as to categorize the graphs by gathering those graphs with the same labels together and isolating those graphs with different labels (e.g. the blue and green arrow) away in the graph updating process. Meanwhile, node representations (e.g. h!) will be closer to the mean vector of their potential corresponding Gaussian functions through node updating process.
4.3 INFERENCE OF NODES
We infer the categories of the nodes in the graph based on the distance between the node represen- tation K obtained from GML and the cluster centers, i.e. mean vector jı of Gaussian functions. We use Goode denote the expected number of node clusters, in traditional clustering methods this is hyperparameter that needs to be set by the user. When Cnode < such K-Means (Ding He 2002) is used cluster Cgraph mean vectors of Gaussian functions to get Cnode cluster centers. Then, the category 2; of the i-th node is determined as follows:
graph, clustering algorithm
& = arg min distance (Tc.
(8)
When Cnode > Cyraph, which is relatively rare in practice, clustering algorithm used cluster node representations h' to Cnode clusters directly.
5 EXPERIMENTS
In this section, to validate the effectiveness of GMGCN under different cases, we first conduct the experiments several synthetic datasets. Then we constructed two real-world datasets, the number of graph categories and node categories these two real-world datasets are both 2.
5.1 BASELINES & EXPERIMENTAL SETTINGS
Since WSGC is new challenge without any bascline work yet, compare the proposed method with three types of most similar methods: Feature Clustering methods without structure informa-
tion (Jain) 2010 McLachlan & Basford 1988 Hinton & Salakhutdinov (006). Graph Clustering
methods Kipf & Welling 2016 Bo et al. (0200) and MIL (Ray & Craven 20055] Andrews et al.,
20026) methods. We also examine the variant of the proposed method ATTGCN: GMGCN with- out GML, we replace node inference with multi-head attention mechanisms in the attentive pooling layer, then distinguish the categories of the nodes by comparing attention scores.
We set 3 = 0.1 in the hierGAT, the experimental results for 3 equals other values are shown in Appendix C.3.2 The parameters are updated using stochastic gradient descent via Adam algo- rithm (Kingma & Ba 2014). The training process is iterated upon 800 epochs for GMGCN. We apply Normalized Mutual Information (NMI) (Strehl & Ghosh] 2002) and Adjusted Rand Index (ARI) (Hubert & Arabie, 1985) to evaluate the graph clustering results on Synthetic Datasets and PHEME Datasets, apply the intersection-over-unioo (IoU) (Jaccard 1912), as our evaluation metric on S3DIS Datasets. We run all methods 10 times to avoid extremes and report the average value with a standard deviation. We only report the best results of each type of method in the sequel due to the page limitations. More detailed baseline descriptions and results are available in Appendix C
5.2 GMGCN ON SYNTHETIC DATA
Synthetic Data Statistics. We generate several synthetic datasets to examine the proposed WSGC problem with various cases. We name each dataset by the number of graph categories and the

---

Under review as a conference paper at ICLR 2022
Table 1: Comparison of different types of methods GC2NC2 (mean(std)).
single graph
methods
orignal nodes
new nodes
new graphs
NMI
ARI
NMI
ARI
NMI
ARI
Feature Clustering Graph Clustering
32.07(1.05 42.19(0.79)
24.42(0.88)
42.86(1.96 45.58(1.41)
80.65(8.18)
85.51(7.96)
87.72(8.52) 74.38(0.00)
85.85(8.47)
78.72(10.47)
84.25(10.33)
MIL
76.74(0.00)
81.67(0.00)
79.64(0.00)
76.61(0.00)
81.53(0.00)
ATTGCN GMGCN
11.08(3.36)
8,53(4.58)
16.60 22)
10.08(3.30)
11.09(5.05 (2.11(3.42)
94.16(0,36)
96.81(0.20)
96.66(0.42) 97.56(0.33)
93.88(0.60)
96.73(0.29)
hierarchical graph
methods
orignal nodes
new nodes
new graphs
NMI
ARI
NMI
ARI
NMI
ARI
ATTGCN GMGCN
11,94(2.77) 77)
3.713333) 17.18(2.55) 55)
10. 10.14(2.92
12.62(2.92) (0.69(0.34)
11.67(3.05) 97.70(0.18)
95.68
97.65 97.65(0.12) 99.01(0.31) (9.28().23)
Table 2: Comparison of different types of methods on Multi-classes Synthetic Datasets (sean(std)).
single graph
GC3NC3
GC4NC4
GCANC2-1
GC4NC2-2
methods
NM1
ARI
NMI
ARI
NMI
ARI
NMI
ARI
Feature Clustering
34.77(0.50)
32.13(0.58)
51.1000.53)
35.17(0.83)
(0,5)
33,2100 89)
28.69(0.58)
26.37 4.41(3 18)
Graph Clustering
14.13(3.28) (0.81(4.2)
37.11(7.01)
35 12(7.77779)
3.88
1,05(2.26)
4.77(2433)
MII.
46.92(0.00)
45.5300.00
61.28(0.00)
47.22(0.00)
AFTGCN
4.06(3.18)
3.62(3.61)
35.67(9.26)
31 48(88888
2.98/2. 12)
3.30(2.33)
2.02(0.92)
(.05(0.93)
GMGCN
51.3(0777)
50.07(1.34)
60.01(5.86)
53.72/9.90)
59.55(2.42)
66.88(3.21)
45.50(3.72)
46.18(5.22)
hierarchical graph
GC3NC3
GCANC4
GCANC2-1
GC4NC2-2
methods
NMI
ARI
NMI
ARI
NMI
ARI
NMI
ARI
ATTGCN GMGCN
9.78(4.60)
7.97(3.52)
36. 16.1668.71)
34.4418. 199
0.40X0.05)
0,34(0.04)
1.72(1.77)
0.94(082))
49.81(1233
47.10(1.95)
62.29(4.94) 57.1917.97)
59.67(3112) 67.18(5.24)
46.86(4.69)
48.00(6.66)
number of nodes, for example, use GC4NC4 to denote synthetic dataset with the number of graph categories as 4 and the number of node categories as 4. More detailed data statistics and data generation process of these synthetic datasets detailed in Appendix C.3.1
Case T. Transductive learning. All graphs are available in the training. Tables I [ 2 show that GMGCN outperforms all the baselines. In particular, it improves NMI and ART by an average of more than 13% and 15%, respectively, compared to the best performing baseline. This indicates a significant improvement of the graph clustering guided by graph labels. Since MIL. cannot handle an unequal number of graph categories and node categories, it has no results on GC4NC2 datasets.
Case Case Inductive learning. Portions of graphs or nodes are available in the training. For the testing of new nodes and new graphs, we sample 20% of the nodes from each graph and 20% of the graphs in GC2NC2 as testing, respectively. GMGCN also outperforms the other baselines as shown in Table T Therefore, GMGCN works for both transductive and inductive settings.
Case 4 With hierarchical graph. We regard the inclusion of hierarchical graph structure as special case (Case 4) of WSGC. As shown in Table [ and Table 2 the hierarchical graph struc- ture promotes both the performance of ATTGCN and GMGCN. This indicates that the structure information between graphs is also beneficial to graph clustering.
Attention vs. GML. We compare the ATTGCN with GMGCN to verify the importance of GML. The results show that GML greatly promotes GMGCN to identify nodes, while the attention mech- anism fails. In addition, a more detailed ablation study is employed to illustrate the importance of each component of GMGCN, due to page limitation we present the experimental results in C.3.3
Visualization. We also visualize the node representations of graphs randomly sampled from GC4NC4 in 2D space by t-SNE (Van Der Maaten 2014). As shown in Fig. 2(a) 2(d) GMGCN clearly distinguishes these 4 node categories but the others fail. This indicates that the node repre- sentations learned by GMGCN are reasonable for WSGC.
Consequently, the out- performmreee of GMGCN for all cases imply that the proposed method is a perfect solution for WSGC.
7

---

Under review as a conference paper at ICLR 2022
(a) Original Features
(b) Feature Clustering
(c) Graph Clustering
(d) GMGCN
Figure 2: 2D visualization of the original node features, the node representations learned by feature clustering, graph clustering, and GMGCN from 4 randomly sampled graphs in GC4NC4. The dif- ferent shapes represent different graphs and the different colors represent different node categories.
5.3 GMGCN ON S3DIS DATA
Data Description. S3DIS (Armeni al. 2016) is composed of 6 large-scale indoor areas, mainly conference rooms, offices and open spaces. Each point is labeled with one of the semantic labels from 13 categories (ceiling, floor, wall, etc. plus clutter). Based on the S3DIS dataset, we construct 13 binary segmentation datasets according to different categories. For each category, the points in the category are annotated with and the rest points are annotated with O. We treat each point as a node in a graph and apply k-NN to construct the edges between points, Each point is represented by 9-dim vector of each point's 3D spatial coordinates and auxiliary features such as color and normalized location. Each graph is annotated with the label that over 50% of the nodes in the graph belong to. Because there is no potential correlation between each graph, this is case without hierarchical graph (Case 4). A detailed data description is presented in Appendix C.4.1
Table 3: Comparison of different types of methods on S3DIS datasets in terms of IoU (%).
training data
Methods
Coiling
Wall
Column
Window
Table
Chair
Sofa
Bookcase
Board
Clutter
mlloU
Feature Clustering
41.71
41.40
32.15
31.55
32.93
33,22
31.70
36.34
32.27
46.99
31.60
30.87
31.64
34.95
Graph Clustering
7.11
7.87
33.46
51.13
34.29
35.05
26.38
49.82
46.70
55.60
38.42
37.97
28.77
34.81
MIL
1.75
0.12
0.19
0,00
0.00
0.00
0.00
0.00
0,00
0.00
0.69
0.00
0.40
0.24
GMGCN
74.04
87.11
42.64
53.15
42.98
47.10
50.34
50.18
53.91
52.83
46.44
41.00
45.44
52.86
test data
Methods
Ceiling
Floor
Beam
Column
Window
Table
Bookcase
Clutter
mloUI
Feature Clustering
39.95
35.64
32.21
27.62
30.50
32.03
30.53
28.69
27.71
31.59
31.59
29.69
29.79
31.35
Graph Clustering
64.57
13.99
36.48
20.39
34.39
19.74
37.22
23.95
18.19
44.10
36.06
31.70
26.46
31.33
MIL
0.03
0.02
0.02
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.05
0.01
GMGCN
65.61
42.84
42.24
33.83
42.61
37.95
31.65
Segmentation Results. We compare the results of each method on the training data and the test data of the S3DIS dataset. As shown in Table the graph clustering methods and GMGCN outper- form feature clustering methods and MIL, which demonstrates that structural information plays an essential role in graph clustering. Furthermore, GMGCN outperforms all the baselines in 12 out of 13 datasets, which explicitly reveals the effectiveness of using graph labels to enhance the training of the graph clustering models. In addition, GMGCN outperforms the best-performing baselines by 18% on the training data and by 13% on the test data in terms of mloU, which further implies strong inductive learning ability of GMGCN. However, GMGCN does not perform well on the Sofa dataset because the dataset containing only 4 graphs in the training is too small for the proposed method to learn enough information from these graphs with the help of graph labels.
5.4 GMGCN ON PHEME DATA
Data Description. PHEME consists of real-life tweets sets, where each set is related to a piece of breaking news (Zubiaga et al. 2016). Every breaking news includes a lot of rumor and non-rumor topics. A detailed data description is presented in Appendix C Based on this dataset, we assume each topic graph, where links between users are formed according to their follows/retweets. The link between two graphs is constructed they have common users. We label the users appearing in more than M rumor topics as abnormal users and the rest as normal users. When M 2,3, 4, the proposed method all achieves the best results, the detailed results are shown in Appendix C.5.2 In this section, only show the results when M 4.
8

---

Under review as a conference paper at ICLR 2022
Table 4: Comparison of different types of methods PHEME datasets (mean(std)).
Charlie Hebdo Ferguson
Germanwings Crash Ottawa Shooting Sydney Siege
Method
NMI
NMI
NMI
NMI
NMI
Feature Clustering
25.46(0.00))
24.56(0.00)
44.59(0.00)
34.56(0.00)
(9.45(0.00)
Graph Clustering MIL
3,26(2.26)
0.57(0.29)
0.66(0.50)
4.49(3.07)
4,93(1.92)
5.69(0.00)
4.08(0.00)
0.61(0.00)
0.60(0.00)
19.68(0.00)
Feature Clustering ffeat aug
25.42(0.00)
24.57(0.00)
44.84(0.00)
34.33(0.00)
19.21(0.00)
Graph Clustering+fed aug
6.08(3.06)
3.99(3.84
4.34(2.25)
6.22(4.15)
6,83(4.28)
Mfa+ aug
22.32(0.000
0.14(0.00)
0.28(0.00)
0.11(0.00)
19.98(0.00)
GMGCN w/o hier GMGCN w hier
47.51(3.27)
48.35(4.08)
48 18.85(
32.58(3.63)
41.00(3.93)
53.26(1.62)
60.78(0.66)
56.63(1.18)
41.21(1.15)
44.37
Method
ARI
ARI
ART
ARI
ART
Feature Clustering
23.46(0.000
23.23(0.00)
42.45(0.00)
32.08(0.00)
16.45(0.00)
Graph Clustering MII.
6.56(6.30)
3.02(2.08)
3.71(1.93)
10.66(7.66 66)
11.78(5.57)
9.38(0.00)
13.93(0.00)
1.10(0.00)
2.09(0.00)
39.51(0.00)
Feature Clustering+feat aug
23.41(0.00)
23.23(0.00)
48.29(0.00)
31,85(0.00)
16.20(0.00)
Graph Clustering+ aug
10.11(6.02)
10.12(7.50
10.1214.47)
8.91(7.99)
12.65(6.99)
MfL+ffcat aug
42.51(0.00)
1.08(0.00)
0,04(0.00)
0.04(0.00)
33.71(0.00)
GMGCN w/o hier GMGCN w hier
52.38(3.15)
55.26(3.21)
54.95(1.00
37.51(2.23)
37.79(2.18)
51.81(1.63)
60.30(0.66)
56.63(1.18)
39.06(1.13)
41.32(0.988
Clustering Results. As shown in Table 4 GMGCN without hierarchical structure (denoted by GMGCN w/o hier) perfectly resolves WSGC with average 13% improvement NMI and 15% improvement on ARI on these five PHEME datasets compared with the best-performing base- line methods. Furthermore, our method with hierarchical structure (denoted by GMGCN w hier) performs best, which indicates that the interconnections among graphs are helpful for inferring the categories of nodes in the graphs. This significant improvement implies that there exist certain applications in the real world that fulfill the statement of WSGC. In contrast, the other methods per- form poorly because WSGC is totally new clustering problem that differs from feature clustering, graph clustering, MIL. It should be noted that the best performing feature clustering method in the PHEME dataset, DBSCAN et al. 1996). is deterministic and no variance caused, so the standard deviation of feature clustering is 0 shown in Table 4
Data Validity. To show that the artificially constructed data is valid, we conduct a comparative ex- periment on PHEME datasets by augmenting the node features with vector, each element of which counts how many graphs a particular category this node belongs to. In Table Method+fea aug means the node features augmented with the vector. Although most clustering methods have been improved by augmenting the node features, they are still generally inferior to GMGCN. This is be- cause although we take into account the number rumor graphs that each node has appeared when labeling the node, these counts do not participate in the supervised learning, so even if we augment the node features with these counts, the traditional methods still cannot identify the node labels. The experimental results demonstrate that our proposed method can deduce the correct results, and it is valuable propose a GNN based method solve such WSGC problem.
DISCUSSION AND FUTURE WORK
In this work, explore interesting and novel problem: Weakly Supervised Graph Clustering (WSGC). In one word, can we identify nodes given the labels of graphs? The proposed WSGC problem has different notions and statements from any of the feature clustering, graph clustering, or multiple-instance learning tasks. To address this new issue. we propose GMGCN with the inte- gration of GMM and GNNs resolve certain cases of WSGC problem. Experimental results on Synthetic datasets and real-world datasets reveal the need for formulating WSGC and the advantage of the proposed GMGCN over other related baselines. Nevertheless, our study is just an initial step towards the weakly supervised graph learning problems while variety of extensions are still poten- tial. For example, can we infer the labels of edges or sub-graphs instead of nodes? Can we detect anomaly nodes other than conducting graph clustering? We hope our study will open up new vein of graph learning and encourage more specifications, solutions, and developments for weakly supervised graph learning.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Charu C Aggarwal and ChengXiang Zhai. A survey of text clustering algorithms. In Mining text data, pp. 77-128. Springer, 2012.
Stuart Andrews, Thomas Hofmann, and loannis Tsochantaridis. Multiple instance learning with generalized support vector machines. In AAAI/IAAI, pp. 943-944, 2002a.
Stuart Andrews, Joannis Tsochantaridis, and Thomas Hofmann. Support vector machines for multiple-instance learning. In NIPS, volume 2. pp. 7, 2002b.
Iro Armeni, Ozan Sener, Amir R Zamir, Helen Jiang, Ioannis Brilakis, Martin Fischer, and Silvio Savarese. 3d semantic parsing of large-scale indoor spaces. Proceedings of the IEEE Confer- ence on Computer Vision and Pallern Recognition, pp. 1534-1543, 2016.
Eduardo Amold, Omar Y Al-Jarrah, Mehrdad Dianati, Saber Fallah, David Oxtoby, and Alex Mouzakitis. A survey on 3d object detection methods for autonomous driving applications. IEEE Transactions on Intelligent Transportation Systems, 20(10):382-33755, 2019.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286
(5439):509-512 1999.
Christopher M Bishop. Pattern recognition and machine learning. springer. 2006.
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In Proceedings of The Web Conference 2020, pp. 1400-1410, 2020.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and lo- cally connected networks on graphs. International Conference on Learning Representations (ICLR2014), CBLS, April 2014, pp. attp-opeerrview, 2014.
Juan Cao, Junbo Guo, Xirong Li, Zhiwei Jin, Han Guo, and Jintao Li. Automatic rumor detection on microblogs: A survey, arXiv preprint
2018.
Marc-André Carbonneau, Veronika Cheplygina, Eric Granger, and Ghyslain Gagnon. Multiple in- stance learning: survey problem characteristies and applications. Pattern Recognition, 77: 329-353, 2018.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Somayeh Sojoudi, Junzhou Huang, and Wenwu Zhu. Spectral graph attention network with fast cigen-approximation. arXiv preprint arXiv:2003.07453 2020.
Veronika Cheplygina, Marleen de Bruijne, and Josien PW Pluim. Not-so-supervised: survey of semi-supervised, multi-instance, and transfer learning in medical image analysis. Medical image analysis, 54:280-296, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Chris Ding and Xiaofeng He. Cluster merging and splitting in hierarchical clustering algorithms. In 2002 IEEE International Conference on Data Mining, 2002. Proceedings., pp. 139-146. IEEE, 2002.
Gary Doran and Soumya Ray. A theoretical and empirical analysis of support vector machine methods for multiple-instance classification. Machine learning, 97(1-2):79-102, 2014.
Khaled El Madawi, Hazem Rashed, Ahmad El Sallab, Omar Nasr, Hanan Kamel, and Senthil Yo- gamani. Rgb and lidar fusion based 3d semantic segmentation for autonomous driving. 20/9
IEEE Intelligent Transportation Systems Conference (FTSC), pp. 7-12. IEFE, 2019.
Francis Engelmann, Theodora Kontogianni, Alexander Hermans, and Bastian Leibe. Exploring spatial context for 3d semantic segmentation of point clouds. In Proceedings of the IEEE Inter- national Conference Computer Vision Workshops, pp. 716-724, 2017.
10

---

Under review as a conference paper at ICLR 2022
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, al. A density-basee algorithm for discovering clusters in large spatial databases with noise. In Kdd, volume 96, pp. 226-231, 1996.
James Foulds and Eibe Frank. A review of multi--nstanee learning assumptions. The Knowledge Engineering Review, 25(1):1-25, 2010.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Searning-Volume Volume 70, pp. 1263-1272. JMLR. org, 2017.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks.
Proceedings of the national academy of sciences, 99(12):7821-7826, 2002.
Matthew B Hastings. Community detection as an inference problem. Physical Review E, 74(3): 035102, 2006.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-507, 2006.
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of (das) 1985.
Paul Jaccard. The distribution of the flora in the alpine zone. 1. New phytologist, 11(2):37-50, 1912.
Anil K Jain. Data clustering: 50 years beyond k-means. Putlern recognition letters, 31(8):551-666, 2010.
Di Jin, Ziyang Liu, Weihao Li, Dongxiao He, and Weixiong Zhang. Graph convolutional networks meet markov random fields: semi-supervised community detection in attribute networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 152-159, 2019.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.6998 2014.
Thomas Kipf, N. and Max Welling. Semi-supervised classification with graph convolutional net- works. In Proceedings of the International Conference on Learning Representations, 2017.
Thomas N Kipf and Max Welling. arXiv:1611.0730,, 2016.
Variational
graph auto-encoders.
arXiv preprint
Loic Landricu and Martin Simonovsky. Large-scale point cloud semantic segmentation with super- point graphs. In Proceedings of the IEEE Conference Computer Vision and Pattern Recogni- fion, pp. 4558 4567, 2018.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE/CVE International Conference on Computer Vision, pp. 9267-9276, 2019.
Zhouhan Lin, Minwei Feng Cicero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. structured self-attentive sentence embedding. arXiv preprint 2017.
Hu Linmei, Tianchi Yang, Chuan Shi, Houye Ji, and Xiaoli Li. Heterogeneous graph attention networks for semi-supervised short text classification. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),, pp. 4821-4833 2019.
Geoffrey McLachlan and Kaye E Basford. Mixture models: Inference and applications to cluster- ing, volume 38. M. Dekker New York, 1988.
Todd K Moon. The expectationn-maxiiizzei algorithm. IEEE Signal processing magazine, 13(6): 47-60. 1996.
11

---

Under review as a conference paper at ICLR 2022
Charles R Qi. Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 652-660) 2017a.
Charles R Qi, Li Yi, Hao Su, and Leonidas Guibas. Pointnet++: Deep hierarchical feature learning on point sets in a metric space. arXiv preprint arXiv:/706.0241: 2017b.
Xiaojuan Qi, Renjie Liao, Jiaya Jia, Sanja Fidler, and Raquel Urtasun. 3d graph neural networks for rgbd semantic segmentation. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5199-5208, 2017c.
Soumya Ray and Mark Craven. Supervised versus multiple instance learning: An empirical com- parison. In Proceedings of the 22nd international conference on Machine learning, pp. 697-704, 2005.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-9055 2000.
Alexander Strehl and Joydeep Ghosh. Cluster ensembles-a a knowledge reuse framework for com-
bining multiple partitions. Journal of machine learning research, 3(Dec):583-617 2002.
Fei Tian, Bin Gao, Qing Cui, Enhong Chen, and Tie- Yan Liu. Learning deep representations for graph clustering. In Twenty- AAAI Conference Artificial Intelligence, 2014.
Laurens Van Der Maaten. Accelerating t-sne using tree-based algorithms. The Journal of Machine Learning Research, 15(1):322133455 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph cnn for learning point clouds. Acm Transactions On Graphics (tog), 38(5): 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Yi Yang, Dong Xu, Feiping Nie. Shuicheng Yan, and Yueting Zhuang. Image clustering using local discriminant models and global integration. IEEE Transactions on Image Processing, 19(10): 2761-2773, 2010.
Xiaoqing Ye, Jiamao Li, Hexiao Huang, Liang Du, and Xiaolin Zhang. 3d recurrent neural networks with context fusion for point cloud semantic segmentation. In Proceedings of the European Con- ference Computer Vision (ECCV), pp. 403-417, 2018.
Chen Zhang, Qiuchi Li, and Dawei Song. Aspect based sentiment classification with aspect-specific 2019.
graph convolutional networks. arXiv preprint
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Xinyi Zhou and Reza Zafarani. Fake news: A survey of research, detection methods, and opportu- nities, arXiv preprint arXiv:1812.00333 2018.
Hua Zhou. A brief introduction to weakly supervised learning. National science review, 5(1): 13, 2018.
Arkaitz Zubiaga, Maria Liakata, and Rob Procter. Learning reporting dynamics during breaking news for rumour detection in social media. arXiv preprint arXiv: 2016.
12

---

Under review as a conference paper at ICLR 2022
A ALGORITHM OF THE PROPOSED METHOD
Algorithm shows the pseudo-codes of GMGCN.
Algorithm GMGCN algorithm
Input:
graph instances set feature matrix of nodes X; numher of graph categories Crraph hyper- parameer:
Gonde
Output: (2( 3.... M,, =(
((1)
s(n)
(N)
(N)
(0, 1,..., Cnode - 1}
MM,
M
while GMGCN not converge do
2: . number of graphs
3: F. = mean vector of e-th Gaussian weight function
4:
for n = ,..... .N do
g(x) graph structure of n-th graph in G
5:
( graph label of n-th graph in G'
6:
M, = number of nodes in ((+)
7:
8:
for i = ,,...,,,. M,. do
Update node representation fúg <- GAT(x!
9:
Update node representation N6 Craph Σ Derraph end for
We (hi, Ro)
Calculate graph representation (() (tt
Update graph representation (n HierGAT(H,))
Calculate consensus loss L [ mn y(m))
end
16:
Update parameters
17:
end while
Cluster Cgraph mean vectors into Cnode mean vectors
for I...., N do
20:
L...., M,, do
Infer the category of each node z(()) < arg min, distance (o pte)
22: end for
23: end for
24: return {$)
(1) M.
(n)
(n)
(N)
(N)
M
B DISCUSSION AND POTENTIAL IMPACT
Since the proposed Weakly Supervised Graph Clustering (WSGC) is new weakly supervised learn- ing task, we used two applications as examples, but in fact this task is also widely existed in drug discovery, 3D vision and natural language processing, etc. Some potential examples are described below.
In drug discovery, thinking of molecules as graphs in which atoms as nodes (the functional groups can also be treated super-nodes) and chemical bonds as edges (Gilmer et al.] 2017]. By applying our method, we can identify the roles certain nodes, sub-graphs, or equivalently functional groups, in each molecular given its chemical or physical properties.
In the field of computer vision, weakly supervised semantic segmentation and object detection are very popular research areas. In many practical scenarios such autonomous driving (Arnold al. 2019 El Madawi et al. 2019) we need to convert the images information into 3D point clouds, which can be further processed with graph learning based approach. Therefore our proposed method has a lot of space for exploration such 3D vision scenarios.
In the field of natural language processing, there is lot of research nowadays that is combined with graph neural networks (Zhagg et al.) 2019 Linmei et al. 2019). For example, treating words, sen- tences paragraphs nodes and articles graphs, if have information about the sentimentality
13

---

Under review as a conference paper at ICLR 2022
of each article, can apply weakly supervised approach identify the sentiment expressed in each words, sentences or paragraphs.
C EXPERIMENTAL DETAILS
In this section, we present the detailed experimental results corresponding the Experiment section. First of all, we introduce the baseline methods mentioned in the Experiment section. Then, we present the detailed results on Synthetic, S3DIS and PHEHE datasets.
C.I BASELINES
Feature Clustering Methods:
K-means (Jain 2010): A classical clustering method that aims to partition data points into clusters which each data point belongs the cluster with the nearest cluster centroid. GMM (MeLachlan & Basford 1988): A probabilistic model that assumes all the data points are generated from a mixture of a finite number Gaussian distributions with un- known parameters.
DBSCAN (Ester et al., 1996): density-based algorithm for discovering clusters in large
spatial databases with noise.
AE (Hinton & Salakhutdinov 2006); A two-stage deep clustering algorithm. We perform
GMM the representations learned by autoencoder.
Graph Clustering Methods:
GAE & VGAE (Kipf & Welling 2016): A structural deep clustering model that combines GCN with the (variational) autoencoder to learn representations. we perform GMM on the representations learned by graph autoencoder.
SDCN (Bo et al., 2020): A structural deep clustering network model that integrates the structural information into deep clustering.
Multiple Instance Learning:
SIL (Ray & Craven 2005): Single-Instance Learning (SIL) is MIL approach that assigns each instance the label of its bag, creating a supervised learning problem but mislabeling negative instances in positive bags.
miSVM (Andrews et al., (002b);: A SVM-based MIL method. After instance labels have been initialized, an SVM classifier trained and used to update the label assignation. These two steps are performed iteratively until the label assignation remains unchanged.
We implement K K-means, GMM and DBSCAN with scikit-learr F] AE, GAE, VGAE, SDCN with Pytorch SIL. miSVM with Python implementation created by (Doran & Ray 2014). To be consistent with related works (Bo al.) 2020), the dimension AE is set to 5050005000-00001111 where d is the dimension of the input data, and the dimension of GAE and VGAE is set to d-256-16 For GMGCN, we adopt independent attention mechanisms for the first GATConv layer and use attention mechanism for the second GATConv layer.
C.2 METRICS
NMI. NMI (Normalized Mutual Information) normalization the Mutual Information score to scale the clustering results between (no mutualinformation) and (perfect correlation). It is calculated follows:
2 T(Y,C) NMI(Y,C) = H(Y) H(C)'
where Y denotes the class labels, C denotes the cluster labels, H(--) means entropy calculated by - P())log(((i), T(Y, (Y,C) C) means mutual information between Y and calculated
hhttps//scikki--lam..og hhops://pytorch.orr/
14

---

Under review as a conference paper at ICLR 2022
by:
M1 C
P(i.j) P(I)
I(Y Σ Pli
(10)
ART The Rand Index (RI) computes similarity measure between clusterings by considering all pairs of samples and counting pairs that are assigned in the same or different clusters in the predicted and true clusterings. is calculated follows:
true posilive true negative
RI truc.positive + false. + taaeeeaallsseee false.negative + true regatine
(11)
(marn The ARI score using the following scheme: ARI (RI Expected (erected_RR) (max(()) (T))
Expected_Rl] The adjusted Rand index is thus ensured to have value close 0.0 for random labeling independently of the number of clusters and samples and exactly 1.0 when the clusterings identical (up a permutation).
mloU loU is a commonly used metric in semantic segmentation measures similarity between finite sample and is defined the size of the intersection divided by the size of the union of the sample sets, i.c. loU = true pwsttivesieee/eeeeee (frue posetiie--tteee + false pos.tiie-stttteee false negative). mloU (mean Intersection-ove over union) common evaluation metric for semantic image segmentation, which first computes the IoU for each semantic class and then computes the average over classes.
C.3 GMGCN ON SYNTHETIC DATA
C.3.1 DATA GENERATION DATA STATISTICS
First, according to the number of node categories Gnode, we generate Cnode synthetic user groups. The edge relationships between users in same user groups are generated by the Barabási-Alber graph model (Barabási & Albert, 1999). We use Gaussian distribution to randomly generate user features. The mean and standard deviation of different types of users are randomly sampled from 5] and [1, 10], respectively. Second, we randomly connect users between user groups to simulate the relationship between different types of users. Third, graph structures composed of different types of users is constructed by sampling users in different user groups. In the case that the number of node categories is equal to the number of graph categories, the label of each graph is determined by the major labels of the users in the graph. In other cases, annotate the same label graphs with the same percentage of users in each category. Finally, we construct the connections between two graphs if they have more than common users. The data statistics of each Synthetic Dataset shown in the Table CI
Table C1: Statistics of Synthetic Datasets.
GC2NC2
GC3NC3
GC4NC4
GC4NC2-1
GC4NC2-2
#Graph categories
2
3
4
#Node categories
2
3
4
2
2
#Graphs
100
60
80
120
100
#Nodes per graph
100
100
100
100
200
#Features
20
15
15
Proportion of nodes
4:1
8:1:1
85:5:5:5
17:3 & 9:1
19:1 & 17:3
C.3.2 DETAILED RESULTS
Table and Table show the detailed experimental results of Table 1 and Table 2 in the Exper- iment section. According to the clustering effectiveness, K-Means is selected as the representative of the feature clustering methods, SDCN is selected as the representative of graph clustering meth- ods and SIL is selected as the representative the MIL methods to be displayed the Experiment section.
15

---

Under review as a conference paper at ICLR 2022
Table C2: Comparison of different methods GC2NC2 (mean(std)). The bold numbers represent the best results.
single graph
orignal nodes
new nodes
new graphs
methods
NMI
ARI
NMI
ARI
NMI
ARI
K-Means
46. 16.10().51)
42.19(0.79)
92.07(1.05)
24.42(0.88)
45.58(1.44
42.86(1.99
GMM
27.86(1.69)
21.59(2.17)
23.01(0.97)
15.63(1.30)
33.00(4.64)
27. 27.66(5.06)
DBSCAN
0.41(0.00)
0.29(0000)
0.00(0.00)
0.00(0.00)
0.30(0.00)
0.56(0.00)
AE
5.11(14.33)
5,36(15.01)
5.39(16.13)
5.29(15.94)
4.73(14.18)
4.96(14.92)
GAE
37.69(3.69)
38.80(4.25)
40.80(4.33)
38.01(4.45)
34.38(4.51)
35.71(5.74)
VGAE
32.06(3.32)
28.63(3.88)
43,90(3.44)
28.24(3.33)
28.93(2.85)
25.18(2.89)
SDCN
80.65(8.18)
85.51(7.96)
85.85(8.47)
87.72(8.52)
78.72(10.47)
84.25(10.33)
SIL
76.74(0.00)
81.67(0.00)
74.38(0.00)
79.64(0.00)
76.61(0.00)
81,53(0.00)
MiSVM
30.66(0.00)
29.25(0.00)
20.34(0.00)
22.16(0.00)
21.05(0.00)
24.37(0.00)
ATTGCN GMGCN
(1.08(3.36)
8,53(4.58)
16. 26.60)
10.08(3.30)
(2.11(3.42)
11,09(5.05)
94.16(0.36)
96.81(0.20)
96.66(0.42)
97.56(0.333
93.88(0.60)
96.73(0.29)
hierarchical graph
methods
orignal nodes
new nodes
new graphs
NMI
ARI
NMI
ARI
NMI
ARI
ATTGCN
11.94(2.77)
8.71(3.34)
17.18(2.55)
10.14().92)
12.62(2.92)
11.67(3.05)
GMGCN
95.68(0.23)
97.65(0.12)
99.01(0.31)
99.28(0.23)
95.69(0.34)
97.70(0.18)
Table C3:
Comparison of different methods on Multi-classes Synthetic dataset (mean(std)). The bold numbers represent the best results.
single graph
GC3NC3
GC4NC4
GC4NC2-1
GC4NC2-2
methods
NMI
ARI
NMI
ARI
NMI
ARI
NMI
ARI
K- K-Means
34.77(0.50)
32.158))58) 51.10(0.53) 35. 17(.83) 34.51(0.95) 33.21(0.89)
28.69(0.58) 26.3770.68)
GMM
32.44(0.81)
29.02(0.95) 46.90(0.86) 29.44(1.18) 19.75(1.11) 16.12(1.50) 21.41(1.99) (7.57
DBSCAN
3.63(0.00) 4.60(0.00) 1.76(0.00) 3.56(0.00) 0.00(0.00)
0.00(0.00)
5.85(0.00) 2.24(0.00)
AE
15.80(1.47) 12.14(..15)
44.34(1.21)
44.74(1.34)
11.37(0.88)
8.28(1.16)
20.79(1.37) 18.51(1.48)
GAE VGAE
11.96(1.18) 7.80(1.71)
21.46(0.78)
(2.54(0.89)
8.23(3.43)
2.47(3.43)
(4.89(1.62)
13.19(2.02)
12.17(1.03) 14.13(3.28) 10.81(4.42)
24.75(1.59) 8.70(1.78)
16.82(1.97)
8.85(0.78)
(.01(0.86)
15.79(1.27)
13.76((.66
SDCN
37.11(7.01I 35.12(7.79)
3.88(1.50)
1.0S(2.26)
4.77(2.43) 4.41(3.18)
SIL
46.92 (0(92)))00 45.53(0.00)
61.28(0.00) 47.22(0.00)
miSVM
35.03(0.00) 30.47(0.00) 45.34(0.00) 31.24(0.000
ATTGCN
4. 4.06(3.18) 3.62(3.61) 35.67(9.22 26) 31.48(8.88) 2.98(..12) 3.30/2.33)
2.02(0.92) 2.05(0.93)
GMGCN
(1.77(0.77) 50.07(1.34) 60.01(5.86) 53.72(9.90) 59.55(2.42) 66.88(3.21) 45.50(3.72) 46.18)2.22)
hierarchical graph
methods
GC3NC3
GC4NC4
GC4NC2-1
GC4NC2-2
NMI
ARI
NMI
ARI
NMI
ARI
NMI
ARI
ATTGCN
9.78(4.60) 7.97(3.52) 36. 16(8.1)) 34.44(8. 19) 0.40(0.05) 0.34(0.04) 1.72(1.57) 0.94(0.82)
GMGCN 49.81(1.23) 47.10(1.95) (2.29(4.94) 57.19(7.97) 53.67(3.12) 67.18(5.24) 46.86(4.69) 48.00(6.66)
Fig. shows the results of GMGCN with hierarchical graph when 3 equals different values. As shown in Fig. [C] when 3 is greater than 0 and less than 0.5, GMGCN is more effective. We choose 3 to be equal to 0.1 in the Experiment section.
16

---

Under review as a conference paper at ICLR 2022
97.00
95.00
Metrics (%)
93.00
91.00
89.00
Original Nodes NMI
New Nodes NMI
New Graphs NMI
Original Nodes ARI
New Nodes ARI
New Graphs
87.00
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
ß
Figure Cl: Results of GMGCN with hierarchical graph when & equals different values on Synthetic dataset.
Table C4: Ablation Study on GC2NC2 (mean(std)).
w/o 2-layer GAT w/o GML
w/o Attentive Pooling w/o hierGAT
w/o consensus loss GMGCN
NMI 26.15().83)
11.94(2.77)
89.22(0.39) 93.89(0.25)
39.20(23.88 24) 50.75(1.19)
95.68(0.23)
ART 29.38(2.14)
8.71(3.34)
50.95(29.98) 54.02(1.83)
97.65(0.12)
C.3.3 ABLATION STUDY.
To verify the importance of each component of GMGCN, we replace each one of the components separately evaluate its performance and compare it with GMGCN. The results are shown Table C4| where 'w/o 2-layer GAT' denotes 2-layer GAT is replaced by 2-layer GCN; "w/o GML' denotes GML-based architecture is replaced by attention-bar based architecture i.e., ATTGCN; 'w/o Attentive Pooling" denotes attentive pooling is repalced by mean pooling; 'w/o hierGAT' denotes hierGAT is repalced by fully conected layers; "w/o consensus loss' denotes consensus loss is repalced by cross entropy loss for graph classification.
The best performance of GMGCN indicates that each component the proposed model plays an important role in predicting the node labels. Specifically, the proposed GML greatly promotes GMGCN to identify nodes, while the attention mechanism fails. When hierGAT replaced with fully connected layers, the experimental results became very unstable with large standard deviations, illustrating the importance of hierGAT. Consensus loss also greatly improves the model effectiveness because it effectively guides the training of the mean vector of Gaussian functions.
C.4 GMGCN ON S3DIS DATA
C.4.1 DATA DESCRIPTION
Distributions of training data and test data in S3DIS datasets are shown in Table C5
In order maintain the balance of training data, we randomly sample some graphs annotated with O, and finally make the number of graphs of different categories in the training set equal. Based on this rule, we can see that objects such as Wall, Ceiling and Floor have sufficient graphs for training, whereas objects such as Sofa and Table have very little graphs for training.
C.4.2 DETAILED RESULTS
Table C6 shows the detailed experimental results of Table 4 in the Experiment section. Since Sofa dataset containing only graphs in the training is too small for the proposed method to learn enough information, GMGCN does not perform well the dataset. Due the large number of instances in
17

---

Under review as a conference paper at ICLR 2022
Table C5: Data distribution of training set and test set in S3DIS datasets.
Training Data
Ceiling
Floor
Wall
Beam
Column
Window
Door
Table
Chair
Sofa
Bookcase
Board
Clutter
1
771
639
2099
7
115
88
404
7
16
2
325
13
437
0
771
639
2099
115
88
404
16
2
325
13
437
total
1542
1278
4198
14
230
176
808
14
32
4
650
26
874
Test Data
Ceiling
Floor
Wall
Beam Column
Window
Door
Table
Chair
Sofa
Bookcase Board Clutter
1
414
417
1270
0
27
93
44
5
283
135
0
6342
6223
1933
24
282
259
787
2401
1783
113
1369
279
4231
total
6756
6640
3203
24
309
352
831
2402
1783
118
1652
279
4366
each bag, miSVM requires an extremely large amount of memory for training, so we cannot show its results.
Table C6: Comparison of different types of methods on S3DIS datasets in terms of IoU (%).
training data
Methods
Ceiling
Wall
Column
Window
Table
Sofa
Bookcase
Clutter
mloU
Kmeans
41.71
41.40
$2.15
31.55
32.93
33.22
31.70
36.34
32.27
46.99
31.60
30.87
31.64
34.95
GMM
43.47
42.37
31.11
26.15
31.42
31.64
33.50
18.18
26.06
32.45
12.41
30.20
31.44
31.80
DBSCAN
30.26
31.68
27.26
33,66
29.58
28.76
28.90
32.80
30.41
31.25
29.54
31.43
31.15
30.51
32.55
32.06
30.58
32.19
33.26
32.62
32.96
32.91
35.45
GAF
36.41
32.12
32.43
21.89
34.11
13.41
32.81
35.62
32.20
16.26
12.94
34.07
32.96
31.86
VGAE
37.47
36.56
$2.36
32.58
33.02
36.12
31.83
34.05
23.37
32.48
33.35
31.65
32.74
32.89
SDCN
7.11
7.87
33,46
51.13
34.29
35,05
26.38
49.82
46.70
$5.60
38.42
37.97
28.77
34.81
SIL
1.75
0.12
0.19
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.69
0.00
0.40
0.24
GMGCN
74.04
87.11
42.64
53.15
42.98
47.10
50.34
50.18
53.91
52.83
46.44
41.00
45.44
52.86
test data
Methods
Ceiling
Floor
Wall
Beam
Column
Window
Door
Table
Chair
Sofa
Bookcase
Board
Clutter
mloU
Kmeans
31.59
29.79
GMM
40.32
36.57
33.53
26.79
33.00
32.86
31.56
28.61
28:21
30.80
31.29
29.75
29.71
31.78
DBSCAN
36.94
37,80
28.64
46.90
37.44
32.60
39.86
43.56
44.91
40.14
35.32
41.47
42.18
39.06
AE
39.95
36.79
32.77
26.02
31.35
33.60
31.97
28.66
28.04
32.50
32.24
30.25
29.83
31.84
GAE SDCN
32.25
32.20
29.76
32.71
32.37
30.86
33.74
30.59
29.96
64.57
13.99
36.48
20.39
34.39
19.74
37.22
23.95
18.19
44.10
36.06
31.70
26.46
31.33
SIL
0.03
0.02
0.02
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.05
0.01
GMGCN
65.61
82.31
44.84
32.95
42.62
42.84
42.24
33,83
42.61
37.19
37.95
38.42
31.65
44.24
C.5
GMGCN ON PHEME DATA
C.5.1 DATA DESCRIPTION
PHEME datase consists of five different news events, all of which attracted substantial attention in the social media and were rife with rumors. The whole dataset is collection of 5802 tweets, of which 1972 were deemed rumors and 3830 were deemed non-rumors. These tweets are distributed differently across the five events, as shown in Table C7 We also present the distribution of abnormal users and normal users across five events when M 2, 3, 4 in Table C8 The features adopted in PHEME dataset are listed in Table C9
C.5.2 DETAILED RESULTS
In PHEME datasets, we label the users appearing more than rumor topics as abnormal users, and the rest normal users. In this part, present the detailed results on PHEME datasets when M = 2, 3, 4. As shown in Table (CO) and CTT. it is obvious that our proposed method can achieve the best effectiveness effectiveness, DBSCAN is selected as the representative of the feature clustering methods, GAE is
PHEME datasets with different M values. According to the clustering
http:://ffssaarr.co///arrre///// dataset of rumours and non-rumours44010619
18

---

Under review as a conference paper at ICLR 2022
selected as the representative of graph clustering methods and SIL is selected the representative of the MIL methods to be displayed in the Experiment section.
Table C7: Distribution of rumors and non-rumors for the five events in the PHEME dataset.
Event
Rumors
Non-rumors
Total
Charlie Hebdo
458(22.0%)
1621(78.0%)
2079
Ferguson
284(24.8%)
859(75.2%)
1143
Germanwings Crash
238(50.7%)
231(49.3%)
469
Ottawa Shooting
470(52.8%)
420(47.2%)
890
Sydney Siege
522(42.8%)
699(57.2%)
1221
Total
1972(34.0%)
3830(66.0%)
5802
Table C8: Distribution of abnormal users and normal users for the five events in the PHEME dataset when M = 2,3.44
Event
Abnormal users
Normal users
Total
M=2
Charlie Hebdo
273(13.1
1806(86.9%
2079
Ferguson
256(22.4%)
887(77.6%)
1143
Germanwings Crash
66(14.1 1))
403(85.9%
469
Ottawa Shooting
288(32.4%)
602(67.6%)
890
Sydney Siege
335(27.4%)
886(72.6%)
1221
Total
1218(21.0%)
4584(79.0%
5802
M=3
Charlie Hebdo
59(2.8%)
2020(97.2%)
2079
Ferguson
50(4.4%)
1093(95.6%
1143
Germanwings Crash
22 (4.7%)
447(95.3%)
469
Ottawa Shooting
64 (7.2%)
826(92.8%)
890
Sydney Siege
101(8.3%)
1120(91.7%)
1221
Total
296(5.1%)
5506(94.9%)
5802
M=4
Charlie Hebdo
23(1.1%)
2056(98.9%)
2079
Ferguson
13(1.1%)
1130(98.999
1143
Germanwings Crash
5(1.1%)
464(98.9%)
469
Ottawa Shooting
15(1.7%)
875(98.3%)
890
Sydney Siege
42(3.4%)
1179(96.6%)
1221
Total
98(1.7%)
5704(98.3%)
5802
19

---

Under review as a conference paper at ICLR 2022
Table C9: Description features used PHEME dataset.
Features
Data Type Description
profile_ux use. background_iman iimage
Bool
Whether the user has background image
default profile image
Bool
Whether the user is using the default profile image
verified
Bool
Whether the user's identity verified by Twitter The code of this user's location in the profile
profile location
Int
followers.count
Int
The number of user's followers
listed count statuses count description
Int
jioned The number of tweets posted by this user
The number of lists this
Int
Bool
Whether the user has personal descriptions
The numher of
who have mutual following relationship with this user
friends_comn
Int
favourites count
The number user's favourites
The time interval between the retweeted the relevant tweet and the original tweet was posted
created time
Int
Table C10: Comparison of different methods on PHEME datasets when M = 2 and M = 3
(mean(std)). The NMI metrie is employed evaluate each method. The bold numbers represent the best results.
M=2
Method
Charlie Hebdo
Ferguson
Germanwings Crash
Ottawa Shooting
Sydney Siege
K-Means
12.90(0.19)
8.49(
25.06(0.57)
20.16(0.
13.88(0.
GMM
10.59(0.26)
6.79(0.19)
20.95(0.99)
16.88(0.55)
12.25(0.32)
DBSCAN
22.47(0.00)
20.22(0000)
32.95(0.00)
27.19(0.00)
16.02(0.00)
AE
11.21(0.31)
12.18(0.66)
21.76(0.75)
15.30(0.66)
11.03(0.44)
GAE
2.20(1.26)
0.63(0.35)
1.79(1.81) (88))
1.84(1.60)
2.01(0.84)
VGAE
1.79(0.87)
0.48(0.68)
1.24(0.69)
0.99(0.81)
(.39(0.54)
SDCN
8.69(2.32)
9.25(2.71)
9.30(1.90)
9.31(2.57)
9.47(0.87)
SIL
8.24(0.00)
2.73(0.00)
0.32(0.00)
3.17(0.00)
10.49(0.00)
miSVM
11.45(0.00)
4.71(0.00)
0.94(0.00)
2.83(0.00)
2.12(0.00)
GMGCN
36.69(1.33)
25.53(1.66)
32.92(1.73)
24.06(2.35)
20.74(1.84)
M=3
Method
Charlic Hebdo
Ferguson
Germanwings Crash
Ottawa Shooting
Sydney Siege
K-Means
10.88(0.12)
5.63(0.00)
17.65(0.18
18.22(0.30)
12.80(0.20)
GMM
8.87(0.26)
2.48(0.35)
15.05(0.55)
14.82(0.46)
11.45(0.60)
DBSCAN
24.54(0.00)
23.40(0.00)
39.81(0.00)
30.88(0.00)
17.61
AE
9.40(0.32)
9.12(0.55)
16.26(0.74)
15.45(0.58)
10.97(0.30)
GAE
3,49(2.26)
0.71(0.68)
1.65(1.76)
3,28(3.01)
1.98(1.38)
VGAE
2.62(0.93)
0.91(0.70)
1.27(0.76)
1.53(1.43)
1.52(0.82)
SDCN
7.61(4.81)
8.78(..43)
9.51(3.69)
9.77(3.20)
9.78(2.42)
SIL
8.24(0.00)
2.73(0.00)
0.00(0.00)
0.48(0.00)
14.86(0.00)
miSVM
15.07(0.00)
1.58(0.00)
0.17(0.00)
0.79(0.00)
0.92(0.00)
GMGCN
43.60(2.54)
37.07(4.58)
40.11(2.72)
27.53(1.54)
37.43(2.30)
20

---

Under review as a conference paper at ICLR 2022
Table C11:
Comparison of different methods on PHEME datasets when M (mean(std)). The bold numbers represent the best results.
Charlic Hebdo
Ferguson Germanwings Crash Ottawa Shooting Sydney Siege
Method
NMI
NMI
NMI
NMI
NMI
K-Means
10.12(0.18)
4.62(0.10)
10.38(0.22)
15.51(0.28)
11.69(0.16)
GMM
8.10(0.29)
3.82(0.18)
8.20(0.49)
(2.27(0.54)
9.93(0.37)
DBSCAN
25.46(0.00)
24.56(0.00)
44.59(0.00)
34.56(0.00)
19.45(0.00)
AE
7.15(0.26)
2.66(0.14)
6.70(0.44)
11.36(0.34)
7.10(0.37)
GAE
3.26(2.26)
0.57(0.29)
0066(0.50)
4.49(3.07)
4.93(1.22)
VGAE
2.08(0.46)
1.08(0.71)
0.77(0688)
4.10(3.93)
1.38(0.72)
SDCN
1.1((0.3)
0.74(0.60)
0.82(0.40)
1.15(0.60)
0.06(0.07)
SIL
5.69(0.00)
4.08(0.00)
0.61(0.00)
0.60(0.00)
19.68(0.00)
miSVM
17.74(0.00)
0.50(0.00)
0.00(0.00)
0.56(0.00)
0.69(0.00)
K-Mcans+feat aug
18.48(0.12)
9.33(0.07)
12.85(0.32)
24.82(0.43)
20.03(0.17)
GMM+feat aug
11.69(0.37)
7.85(0.21)
9.64(0.76)
(5.89(0.50)
13.0910.43)
DBSCAN+feat aug
25.42(0.00)
24.57(0.00)
44.84(0.00)
34.33(0.00)
19.21(0.00)
AE+feat aug
10.93(0.26)
13.20(0..6)
12.94(0.53)
9.94(0.42)
10.05(0.49)
GAE+feat aug
6.08(3.06)
3,99(3.84)
2.34(2.25)
6,22(4.15)
6.83(4.28)
VGAE+feat aug
5,49(2.29)
3,45(2.90)
2.67(2.08)
5.83(4.09)
5,45(3 44)
SDCN+feat aug
14.66(2.42)
14.93(4.43)
39.14(11.78)
18.98(2.36)
11.002.07)
SIL+feat aug
22.32(0.00)
0.14(0.00)
0,28(0.00)
0.11(0.00)
19.98(0.00)
miSV MrfVM+ aug
17.74(0.00)
0.50(0.00)
0.00(0.00)
0.56(0.00)
0.69(0.00)
GMGCN w/o hier
47.51(3.27)
48.35(4.08)
48.85(2.14)
32.58(3.63)
41 41.00X.993
GMGCN hier
53.26(1.62)
60.78(0.66)
56.63(1.18)
41.21(1.15)
(4.37(0.98)
Method
ARI
ARI
ARI
ARI
ARI
K- Means
8.20(0.20)
3.33(0.15)
9.14(0.29)
13.27(0.30)
8.75(0.19)
GMM
5.52(0.40)
2.06(0.24)
6.21(0.69)
9,00(0.65)
6.35(0.48)
DBSCAN
23.46(0.00)
23.23(0.00)
42.45(0.00)
32.08(0.00)
16.45(0.00)
AE
4.36(0.31)
0.34(0.24)
4.08(0.57)
7.76(0.50)
2.73(0.45)
GAE
6.56(6.30)
3.02(2.08)
3.71(1.93)
10.66(7 7.68)
11.78(5.57)
VGAE
2.30(1.74)
4.04(2.24)
3.41(2.57)
9.56(8.68)
2.003.20
SDCN
1.03(1.00)
0.74(0.90)
0,92(0.66)
0.76(1.01)
0.27(0.36)
SIL miSVM
9.38(0.00)
13.93(0.00)
1.100.00)
2.09(0.00)
39.51(0.00)
32.28(0.00)
2.80(0.00)
0.01(0.00)
0.31(0.00)
1.88(0.00)
K-Means+ aug
(8.01(0.14)
9.64(0.09)
11.96(0.34)
23.85(0.45)
18.58(0.21)
GM+feat aug
10.06(0.42)
7.57(0.29)
7.83(0.93)
13.40(0.64)
10.29(0.50)
DBSCAN+feat aug
23.41(0.00)
23.23(0.00)
48.29 08)
31,85(0.00)
16.2010.00)
AE+feat aug
7.67(0.28)
11.42(0.44)
9.57(0.67)
4.92(0.59)
5.02(0063)
GAE+feat aug
10.11(6.02)
10.12(7.56)
10.12(4.47)
8.91(7.99)
(2.65(6.99)
VGAE+feat aug
6.61(5.27)
9,15(6,51)
7,00(5,31)
11.46(8.) 15)
SDCN+feat aug
10.73(2.96)
10.96(4.38)
36.47(12.04)
14.00(2.71)
4.84(2.47)
SIL+fcat aug M+feat aug
42.51(0.00)
1. 1.8(0.00)
0.04(0.00)
0.04(0.00)
33.71(0.00)
32.28(0.00)
2.80(0.00)
(0.00))00)
0.31(0.00)
1.88(0.00)
GMGCN w/o hier GMGCN
52.38(3.15)
55.26(3.21)
54,95(1.022
37.51(2.23)
37.79(2.18)
51.81(1.63)
60.30(0.66)
56.63(1.18)
39.06(1.13)
41.32(0.98)
21


Reviews:
[{"review_id": "oAi_eIb0yDd", "reviewer": "Reviewer_oDis", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Even though this manuscript reads well and tries to define a new problem and a solution for the proposed problem, I have some major concerns described below.\n\nAccording to the definition of the proposed problem, one should have node features, node labels, interactions between the nodes, the graph labels, and possibly the higher-level interactions between the graphs. I wonder if one can grasp all this rich information in practical applications. More importantly, it is not clear how the graph label affects the predictions of node labels. In experiments, the authors consider only one type of real-world data from Twitter, which does not include the interactions between graphs. Without the interactions between graphs (i.e., the hierarchical graph), we can treat each graph as an independent graph and apply well-known graph clustering or node classification methods such as GCN, GraphSAGE or GIN.\n\nFor the examples or applications of the proposed problem, the authors mention detecting frauds or abnormal users. Since there is substantial literature for anomaly detection, the proposed method should have more general applications other than anomaly detection. Unfortunately, it is hard for me to think of realistic scenarios or interesting applications of the proposed method. \n\nOverall, the proposed method seems to make a simple problem more complicated. To make the proposed method convincing, more general practical applications should be shown where all the inputs the problem require are provided. Also, the authors should show whether each of the components plays a critical role in predicting the node labels and analyze how each component affects the results.\n\n* Minor comments: In Section 3.1, $d$ is not defined.", "summary_of_the_paper": "This manuscript proposes a problem defined as weakly supervised graph clustering. Given a set of graphs and node features, the problem is to predict node labels in each of the graphs. Some variations can be made depending on selecting the targets whose labels are supposed to be predicted.", "summary_of_the_review": "I reject this paper because (1) it is hard to find practical applications of the proposed method; one can solve the problem more easily in many practical applications, (2) it is not clear how each of the inputs affects the predictions, (3) the experiments do not include diverse real-world datasets.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h6CBQlaPu3K", "reviewer": "Reviewer_PUKs", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strengths:\n1. The problem is well-motivated.\n2. The proposed method is reasonable.\n3. Extensive experiments are given.\nWeaknesses:\n1. The comparison methods are not convincing. It is better to employ some recent techniques.\n2. The technique is not as novel as the authors claim.", "summary_of_the_paper": "This paper investigates the graph clustering problem with the aid of graph labels. GMM and GCN are used to solve this problem. A new loss is also designed. Extensive experiments are conducted to show the effectiveness of the proposed method.", "summary_of_the_review": "1. There are some closely related works in the literature. The authors should discuss the contributions more clearly. \n2. Does this paper \"Semi-Supervised Graph Classification: A Hierarchical Graph Perspective\" study the same problem？\n3. Is the proposed method related to multi-view/multi-layer graph clustering?\n4. There are some writing errors.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WRzCjL491sE", "reviewer": "Reviewer_r2ym", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strengths\n- The proposed methods outperform baseline models on the given datasets and synthetic datasets.\n- Two levels of graphs (one for graphs of multiple categories and the other for the hypergraph) are used and those levels are connected through Gaussian Mixture embeddings.\n\nWeaknesses\n- Despite the complicated process and a lot of notations, definitions, relationships, and explanations for notations are not sufficient or there exist some typos so that the manuscript is not easy to follow. \n- Not knowing the number of clusters is a common problem, but the guidance to tackle that problem is not suggested.\n- Despite the long and complicated process, the contribution or the necessity of each step is not clear. Ablation study would be helpful.\n- In particular, the contribution of weak supervision is not clear. Without the clear evidence, a weakly supervised method would not be verified over an unsupervised method.\n\nDetails\n- Eq (4) is not well-defined. First of all, the number of clusters should be C_node, not C_graph. Second, the output of w_c seems to be the vector, while Eq (4) does not necessarily indicate the full Gaussian model. Would \\Theta_GLM indicate the inverse of covariance matrix so that Eq. (4) means the entriy-wise Guassian model?\n- Authors describe that Eq. (5) does not have the training parameters, but \\alpha^{heir} itself contains many weight coefficients. The description should be clearer to clarify the distinction between training parameters and the others.\n- Consensus loss is based on the linear sum of the distance to cluster center and the distance to graph center. Then, what is the role of weak supervision if there is no use of true labels?\n- GLM-based clustering methods needs to be also compared as baseline methods.", "summary_of_the_paper": "Authors provide the framework that combines Graph Attention Networks (GAT) and Gaussian Mixture Models (GMM) to tackle the weakly supervised graph clustering model. In particular, the consensus loss, a new loss function designed by the authors, is used for the entire framework. Authors also address different kinds of weak supervision settings and show the performance of the proposed framework for each case on synthetic datasets. ", "summary_of_the_review": "While each step of the entire process is fair, the necessity of each step is not sufficiently verified. Despite the hypergraph setting and the weak supervision setting, authors show the experiments on multi-view graphs or partitioned graphs (for real-world datasets), and do not show the benefits of weak supervision. Furthermore, the proposed method should be compared with Guassian-embedding based models.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PFBnA0SR4Go", "reviewer": "Reviewer_inpd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Pros:\n\n1. The paper is well organized, and generally easy to read.\n2. The idea of incorporating coarse-grained graph label to assist graph clustering is somewhat interesting, and may be useful in some specific scenarios.\n3. Experiments also demonstrating the superiority of the proposed WSGC task over the traditional GC task.\n\n\nCons: \n1. The current title of the submission seems overclaimed. As weakly supervised graph clustering may also include some other settings such as partial supervision, distant supervision, etc, it seems overclaimed to name the paper title as weakly supervised graph clustering. To me, it will be much better to highlight incorporating graph-level side information, which is the key contribution of this paper.\n2. Although the graph labels have been shown to bring significant performance gains in their experiments, it is not clear to me what kind of graph labels are effective for graph clustering? Are they task specific? Do we need to manually design such graph labels?\n3. In Table 3, it is interesting that for most categories the GMGCN approach achieves the best performance, but for the sofa category, its performance is much lower than the baselines. Could you please give some analysis to explain the reasons of the performance difference?\n4. In Figure 1, what does node updating denote?\n", "summary_of_the_paper": "This paper studies a new problem named weakly supervised graph clustering (WSGC), where the goal is to cluster nodes better with some graph-level side information, i.e., graph labels.\n\nMost previous studies for graph clustering primarily consider node/edge information and their connections, but ignore graph-level side information, which might be easily accessible in real scenarios. Inspired by this observation, this paper proposed to incorporate graph-level labels into graph clustering, and formulate the new problem as weakly supervised graph clustering. Based on the new problem, the authors further proposed a simple yet effective framework based on Gaussian mixture model (GMM) and graph convolutional network (GCN) named Gaussian Mixture Graph Convolutional Network (GMGCN) for learning node representations. Moreover, they also introduced a consensus loss for graph labels and employed Gaussian Mixture  Layer to infer the category of each node.\n\nExperiments on both synthetic and real-world datasets demonstrate the effectiveness of the proposed GMGCN approach.\n", "summary_of_the_review": "Overall, I think the idea of incorporating coarse-grained graph label to assist graph clustering is intuitive and somewhat interesting, and the proposed model also generally makes sense to me. But I still have some concerns regarding the title, the choice of graph labels, and the performance analysis.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9-ctT56j7m", "reviewer": "Reviewer_Khg3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strength\n\n1) The paper is well written and structured. Four cases were presented, and comprehensive experimental results on synthetic data are presented for each of the four cases.\n2) The twitter example provides a good practical use case of the proposed algorithm.\n\nWeakness\n\nI'd love to have clarity on a few things:\n1) Is it assumed that C_node < = C_graph? Do we assume C_node is known? When C_node is unknown, how do we determine it? \n2) Is there a real world example where interconnections among graphs exist and are helpful for graph clustering? Given both real-world datasets are single graph case, I can't think of an example that puts case 4 in use.\n3) It would be more clear to have an algorithm part, where inputs, outputs, and steps of algorithms are presented.\n4) It is not clear to me why we need two datasets of GC4NC2 for experiments and the major difference between them.\n5) Is there a minimum number of graphs that the authors recommend for the proposed algorithm? The authors claim that the sofa example didn't do well (relative to other methods) due to small sample size.\n\nMinor points\n1) typo: page 3, section 3.1, where C_{node} -1 is the expected number of node categories --> where C_{node} is the expected number of node categories\n2) It would be more clear if the authors explain NMI and mIoU in the last paragraph of the introduction section.", "summary_of_the_paper": "The authors propose a new Gaussian Mixture Graph Convolutional Network approach to perform graph clustering with the assistance of graph labels. Experimental results suggest that the addition of graph labels boosts performance over traditional clustering methods, and over multiple-instance learning. ", "summary_of_the_review": "The problem is novel and the authors have demonstrated that having coarse-grain labels on the whole graph can assist with clustering on a node level. The comments for improvement are mainly on clarifying some details of applying the proposed algorithm.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Existing methods for graph clustering usually use node/edge information, but ignore graph-level information. This paper proposes incorporating graph-level labels into graph clustering and formulating the new problem as weakly supervised graph clustering.  The paper further proposes Gaussian Mixture Graph Convolutional Network (GMGCN) framework for the task.  Experimental results on several datasets demonstrate the effectiveness of the method.

The authors are very active in answering questions by the reviewers.  They have successfully addressed some of the issues. However, there are still questions that remain unaddressed. The submission is not of the quality of ICLR papers.

Strength
* A new method is proposed.
* The proposed methods outperform baseline models on the given datasets and synthetic datasets.

Weakness
* The explanations are not clear enough.  Although the authors provide detailed responses to the reviews,  the problems indicated by the reviewers are still not well addressed.
* The proposed method seems to be too complicated.
* It is not clear why the proposed method works.
* The problem studied might not be realistic.

----
Here is a summary of the reviewers' final comments.

* Reviewer oDis slightly increased the score。

* Reviewer r2ym says“I read responses to my concerns and others, but except for some clarifying statements and notations, authors' responses are not convincing enough. Also, while I now understand the concept of proposed work better than before, I do not think that it is explained and presented well enough.”

* Reviewer inpd says “would like to keep my original score”.
Decision: Reject