Inverse Graph Identification: Can We Identify
Node Labels Given Graph Labels?

In many scenarios, the objects with their features are connected by their interactions as graphs. By analyzing these edge connections and node features throughout various graphs, a graph identification (GI) problem is formed to predict the information or properties of the graphs, such as labels or scores of the target graphs. Many studies have been developed on GI, such as graph classification li2019semi ; shi2000normalized and graph regression pujara2013knowledge . Formally, methods for GI aggregates the information from nodes and edges to predict or summarize the information of the whole graph. However, it is much more interesting to consider an inverse problem which has never been proposed: Can we use the information of graphs to infer the information of nodes or even edges and sub-graphs? In another word, given the labels of graphs, how to figure out the categories of nodes, edges, or sub-graphs?

This problem is interesting and very common in the real world. In social media, for example, thinking of hot events that are widely discussed in the form of graphs where users involved as nodes and the co-following relationship among users as edges, it is interesting to think how to pick out the malicious users from the mass of users with only the labels of these event topics such as the authenticity of each topic zhou2018fake ; cao2018automatic . In drug discovery, for another example, thinking of molecules as graphs in which atoms as nodes and chemical bonds as edges, we attempt to identify the roles of certain sub-graphs, or equivalently functional groups, in each molecular given its chemical or physical properties gilmer2017neural ; ma2020dual . In a programming language, for the last example, thinking of control flows for programs as graphs by considering statements as nodes and control flows as edges, can we detect the problematic statements if we have already known which program has bug or not lu2005bugbench ?

All these problems can be defined as a general problem as Inverse Graph Identification (IGI) that identifies the nodes in graphs based on the information of graphs. The main difficulty of the IGI task is that the node labels are inaccessible so that all available information for the training model only comes from the labels of graphs. Namely, it is a node identification task where the available training labels are much coarser-grained than the node labels we want to fit. It seems this problem can be resolved from the present perspective of node clustering girvan2002community or node identification kipf2017semi . However, they are different from the problems that we attempt to address. Unlike node clustering which only conducts clustering based on node features or graph structures, IGI is better guaranteed by the given label information of graphs, which, we will demonstrate, closely influences the clustering results. It is also different from the node identification task because IGI does not contain any node labels for training. Another similar concept to our IGI is Multiple-Instance Learning (MIL) carbonneau2018multiple that adopts global labels of bags to identify the labels of local instances. However, MIL assumes that each instance is i.i.d. and there are no edge connections involved. Therefore, it is interesting and important to study the IGI problem as a set of new challenges and seek new solutions for it.

In this paper, we formally define IGI and address out its different problem statements as a set of new challenges. Meanwhile, we focus on a particular study of IGI: A node clustering task by making use of graph labels and node features with an assistance of a hierarchical graph girvan2002community that further characterizes the relations among graphs. To address this particular task, we propose a novel model based on Gaussian mixture model (GMM) and graph convolutional network (GCN) named as Gaussian Mixture Graph Convolutional Network (GMGCN). First, the features of each node are updated through the Graph Attention Network (GAT). Then the node features are aggregated by a Gaussian mixture layer (GML) and a new attention pooling layer proposed in the paper. After obtaining the graph representations, we adopt a hierGCN to classify the graphs. Specifically, we design a consensus loss that plays a key role in the training process. Finally, a node clustering is carried out according to the parameters of GML. The main contributions are as follows: 1. New problem:We introduce a new problem called Inverse Graph Identification (IGI), which tries to identify the nodes in graphs based on the labels of graphs, and we take a formal discussion of the variants of IGI 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 a particular study of IGI problem. To the best of our knowledge, this is the first work to achieve node 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 that this consensus loss greatly improves the model effect.

We validate the proposed GMGCN on various synthetic datasets based on different problem statements and a real-world dataset. The results demonstrate that the proposed method is suitable to solve the IGI task.

Graph Identification. Recently, there is 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 te al. gilmer2017neural which re-generalize several neural network and graph convolutional network approaches as a general "message-passing" architecture. Many kinds of GCN bruna2014spectral ; defferrard2016convolutional ; kipf2017semi actually deliver different message propagation functions for GCN. Among them, Graph Attention Networks (GAT) velivckovic2017graph first leverages learnable self-attentional layers to aggregate weighted neighbors’ information. All of these methods obtain the appropriate node representation for node identification tasks. But to cope with the GI problem, a compact representation on graph level should be utilized. Therefore, pooling strategies are proposed to integrate information over the node representations wu2020comprehensive , such as max/min pooling defferrard2016convolutional , SortPooling zhang2018end , and so on. In addition, Lin et al. lin2017structured propose an learnable attention pooling for weighted averaging of node representations. Although several studies have researched the graph identification problem, current researches are still lack of studies about Inverse Graph Identification.

Graph Clustering. Graph clustering, a fundamental data analysis task that aims to group similar nodes into the same category, has similar goals as IGI problem. Many real-world applications are cast as graph clustering shi2000normalized ; white2005spectral ; hastings2006community ; kim2006customer . The major strategy of graph clustering is to perform simple clustering algorithms such as $K$-means jain2010data or GMM mclachlan1988mixture on the features embedded from graph embedding wang2017community . With greatly successful achievements of deep learning, more graph clustering studies have resorted to deep learning to learn embedding that capturing both node features and structural relationships wu2020comprehensive . Researchers employ the stacked sparse autoencoder tian2014learning , the variational autoencoder kipf2016variational , or the combination both autoencoder and GCN bo2020structural to obtain graph representations for clustering. Nevertheless, these graph clustering methods do not perform well on IGI due to the lack of attention to graph labels.

Multiple-Instance Learning. Another task that has a similar definition to IGI is Multiple-Instance Learning (MIL). MIL is a variant of inductive machine learning, where each learning example consists of a bag of instances instead of a single feature vector foulds2010review . When obtaining local instances annotations is costly or not possible, but global labels for bags are available, MIL is utilized to train classifiers using weakly labeled data. It has received a considerable amount of attention due to both its theoretical interests and its applicability to real-world problems dietterich1997solving ; andrews2002multiple ; cheplygina2019not ; pinheiro2015image . For example, Wu et al. wu2015deep propose deep MIL which adopts max pooling to find positive instances for image classification and annotation. Although these MIL methods learn a classifier from the labels of bags to achieve the instance classification, these MIL methods ignore the structural information among instances so that they are not suitable for IGI.

Gaussian Mixture Model. In addition, as a core part of the proposed GMGCN model, GMM is a parametric probability density function for a weighted sum of Gaussian component densities mclachlan1988mixture . It is commonly used to find underlying clusters in data samples bishop2006pattern . Generally, the GMM parameters are estimated using the iterative Expectation-Maximization (EM) moon1996expectation algorithm from training data. In this paper, we integrate the GMM into GCN to establish a solution for IGI and update the GMM parameters using stochastic gradient descent.

Notations. We denote a set of graph instances as $G=\{(\mathcal{G}^{(1)},y^{(1)}),\dots,(\mathcal{G}^{(N)},y^{(N)})\}$ with $N$ graphs, where $\mathcal{G}^{(n)}$ refers to the $n$-th graph instance and $y^{(n)}\in\{0,1,\dots,C-1\}$ is the corresponding graph label of $C$ different categories. We denote by $\mathcal{G}^{(n)}=(\mathbb{V}^{(n)},\mathcal{E}^{(n)})$ the $n$-th graph instance of size $M_{n}$ with nodes $v^{(n)}_{i}\in\mathbb{V}$ and edges $(v^{(n)}_{i},v^{(n)}_{j})\in\mathcal{E}^{(n)}$, by $\mathrm{\mathbf{X}}^{(n)}=\{x^{(n)}_{1},\dots,x^{(n)}_{M_{n}}\}\in\mathbb{R}^{M_{n}\times d}$ the feature matrix of nodes $\mathbb{V}^{(n)}$, and by $\mathrm{\mathbf{A}}^{(n)}\in\{0,1\}^{M_{n}\times M_{n}}$ the adjacency matrix which associate edge $(v^{(n)}_{i},v^{(n)}_{j})$ with $A^{(n)}_{i,j}$. We denote by $\{z^{(n)}_{1},\dots,z^{(n)}_{M_{n}}\}\in\{0,1,\dots,C-1\}$ the potential labels of nodes $\mathbb{V}^{(n)}$, which are invisible to the model training. In addition, we denote by $\mathrm{\mathbf{A}}^{hier}\in\{0,1\}^{N\times N}$ the adjacency matrix of the links among graphs if the graphs in $G$ contain inter-connections. Then, $\mathrm{\mathbf{A}}^{hier}=\mathrm{\mathbf{I}}$ if no relationships among graphs.

Problem Statement. The Inverse Graph Identification problem is defined as: Given a set of graph-label pairs $G$ and node features $\mathrm{\mathbf{X}}$, how to infer each label of the $i$-th nodes in the $n$-th graph, $z^{(n)}_{i}$, where $n\in\{1,\dots,N\}$ and $i\in\{1,\dots,M_{n}\}$? Under the definition of IGI, there are some different cases that could be extended from the problem as new tasks.

There are more different cases under IGI problem. For example, how to infer a node score instead of a node label? We will discuss more cases in Appendix A. In this paper, we focus on the IGI problem that aims to infer the labels of the nodes. In the Experiments section, we will examine the proposed method and the baselines under all the above cases.

In this section, we first introduce the preliminaries related to the proposed model, then we discuss two key components of GMGCN: GML and consensus loss.

In this section, we first conduct the experiments on synthetic data to validate the effectiveness of our proposed model under different problem cases. Then, we construct a real-world dataset based on the public rumor dataset called PHEME¹¹1https://figshare.com/articles/PHEME_dataset_of_rumours_and_non-rumours/4010619 zubiaga2016learning , the proposed method and the comparisons are evaluated on the constructed dataset.

In this work, we explore an interesting and novel problem: Can we identify nodes given the identifications of graphs? In one word, can we Invert the Graph Identification? The proposed IGI problem has totally different notions and statements from any of the node clustering, graph clustering, or multiple instance learning tasks. To address this new issue, we propose GMGCN with the integration of GMM and GNNs to resolve certain cases of IGI problem. Experimental results on Synthetic data and real-world data reveal the need for formulating IGI and the advantage of the proposed GMGCN over other related baselines. Nevertheless, our study is just an initial step towards the IGI problem while a variety of extensions are still potential. For example, can we infer the labels of edges or sub-graphs instead of nodes? Can we detect anomaly nodes other than conducting node clustering? We hope our study will open up a new vein of graph learning and encourage more specifications, solutions, and developments for IGI.

Nowadays, many studies have been developed on Graph Identification (GI), such as graph classification and graph regression. However, the inverse problem of using the information of graphs to infer the information of nodes or even edges and sub-graphs has never been raised. In this paper, we present a new challenge named as Inverse Graph Identification (IGI). As opposed to GI, IGI mainly explores whether we can identify nodes given the labels of graphs they belong to. We also analyze various tasks belonging to the IGI problem so that more researchers can participate in the research of the IGI problem. By studying the IGI problem, many graph learning problems will be solved in a more appropriate and efficient way. The broader impact of our research can be summarized below:

For social media community: Through the research of social media tasks on IGI problem, different types of information communicators can be identified more accurately. For example, media reporters can use the proposed model to find appropriate interviewees, advertisers can discover the users in social networks for accurate advertising.

For biology and chemistry community: Biologists can divide proteins into groups according to the different interactions of proteins, and then use our method to find proteins with specific functions. Chemists can employ our method to discover functional groups with special properties.

For network security community: By dividing different people into groups, network security officers can utilize our method to discover suspicious users on the LAN, and can also employ our method to find suspicious operations or applications by grouping different operations or software together.