Nothing Special   »   [go: up one dir, main page]

CN111476261A - Community-enhanced graph convolution neural network method - Google Patents

Community-enhanced graph convolution neural network method Download PDF

Info

Publication number
CN111476261A
CN111476261A CN201911288719.9A CN201911288719A CN111476261A CN 111476261 A CN111476261 A CN 111476261A CN 201911288719 A CN201911288719 A CN 201911288719A CN 111476261 A CN111476261 A CN 111476261A
Authority
CN
China
Prior art keywords
graph
function
matrix
neural network
representation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN201911288719.9A
Other languages
Chinese (zh)
Inventor
刘彦北
王祺
肖志涛
张芳
耿磊
吴骏
王雯
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Tianjin Polytechnic University
Original Assignee
Tianjin Polytechnic University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Tianjin Polytechnic University filed Critical Tianjin Polytechnic University
Priority to CN201911288719.9A priority Critical patent/CN111476261A/en
Publication of CN111476261A publication Critical patent/CN111476261A/en
Pending legal-status Critical Current

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00Pattern recognition
    • G06F18/20Analysing
    • G06F18/21Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
    • G06F18/214Generating training patterns; Bootstrap methods, e.g. bagging or boosting
    • G06F18/2155Generating training patterns; Bootstrap methods, e.g. bagging or boosting characterised by the incorporation of unlabelled data, e.g. multiple instance learning [MIL], semi-supervised techniques using expectation-maximisation [EM] or naïve labelling
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00Pattern recognition
    • G06F18/20Analysing
    • G06F18/24Classification techniques
    • G06F18/241Classification techniques relating to the classification model, e.g. parametric or non-parametric approaches
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00Computing arrangements based on biological models
    • G06N3/02Neural networks
    • G06N3/04Architecture, e.g. interconnection topology
    • G06N3/045Combinations of networks
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06NCOMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00Computing arrangements based on biological models
    • G06N3/02Neural networks
    • G06N3/08Learning methods
    • G06N3/084Backpropagation, e.g. using gradient descent
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06QINFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q50/00Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
    • G06Q50/01Social networking

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • General Physics & Mathematics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Evolutionary Computation (AREA)
  • General Engineering & Computer Science (AREA)
  • Computing Systems (AREA)
  • Health & Medical Sciences (AREA)
  • General Health & Medical Sciences (AREA)
  • Computational Linguistics (AREA)
  • Evolutionary Biology (AREA)
  • Biophysics (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Biomedical Technology (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Molecular Biology (AREA)
  • Business, Economics & Management (AREA)
  • Economics (AREA)
  • Human Resources & Organizations (AREA)
  • Marketing (AREA)
  • Primary Health Care (AREA)
  • Strategic Management (AREA)
  • Tourism & Hospitality (AREA)
  • General Business, Economics & Management (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

The invention provides a community-enhanced graph convolution neural network method, which comprises the following steps: (1) inputting a feature matrix formed by node feature vectors of graph data and an adjacency matrix of a graph; (2) calculating a modularity matrix of the graph; (3) extracting features of the graph data by adopting a graph convolutional neural network, and obtaining a final graph representation by the last layer of hidden representation through a softmax function; (4) defining a target function for detecting a community structure and fusing the target function and a cross entropy function into a unified loss function; (5) parameters are optimized, and a loss function is minimized, so that the graph is represented by an iteration updating graph. The method can acquire the local and global structure information of the graph to learn the graph representation at the same time, and can be widely applied to the technical fields of social networks, traffic networks, citation networks and the like which need to analyze irregular graph data.

Description

Community-enhanced graph convolution neural network method
Technical Field
The invention belongs to the field of data mining, and provides a method for a community-enhanced graph convolution neural network, which can be used for semi-supervised classification problems represented by a citation network, a social network and the like.
Background
The graph data has an irregular and changeable data structure and is used for representing various objects and the mutual relations among the objects, and the graph data can be applied to a plurality of fields such as social networks, traffic networks, biochemical molecular networks and the like. Graph data representation has become an increasingly popular area of research. The graph neural network is the most popular graph representation method based on the deep learning technology, and particularly, the graph convolution network method is used for popularizing convolution operation from traditional image data to graph data, and has shown remarkable learning capability.
Graph convolutional neural network methods can be divided into spectral-based and spatial-based methods. The spectral-based approach defines the graph convolution operation by the spectral representation of the graph, which can be interpreted as de-noising, rather than introducing a filter to define the graph convolution from the perspective of graph signal processing. The space-based method defines the convolution operation of the graph through the spatial relation of the nodes, and an operator directly defining the neighborhood nodes represents the graph convolution as aggregating the characteristic information from the neighbor nodes.
However, most graph convolutional neural network approaches focus primarily on the local structure of the network, i.e., the relationship or similarity of nodes to neighbor nodes, while global structures are ignored as an important feature of another aspect of the network. Specifically, the graph convolution neural network performs convolution on the graph by aggregating information of neighboring nodes, and fuses the relationships between the nodes to extract local features of the graph. However, the graph convolution neural network model does not take into account the global structure, i.e., the relationship between communities formed by nodes. Nodes have dense connections within their communities and sparse connections between communities, e.g., users belonging to the same organization have close relationships and users of different organizations have distant relationships in a social network. The representation of nodes within a community should be more similar than the representation of nodes between different communities.
In order to solve the problems, the invention provides a community enhanced graph convolution neural network method.
Disclosure of Invention
The invention provides a community-enhanced graph convolution neural network method, which can simultaneously acquire local and global information of a graph and learn an effective graph representation. Local feature information of the graph is extracted through a main framework of a graph convolution neural network model, and global feature information is extracted through introducing constraints of community structures into the network. The result shows that the method is superior to the existing graph convolution neural network method.
The technical scheme for realizing the invention comprises the following steps:
step 1, inputting a feature matrix X ∈ R consisting of node feature vectors of graph datan×mThe abutting matrix of the figure A ∈ Rn ×nN represents the number of nodes, m represents the number of features;
step 2, calculating a modularity matrix B ∈ R of the graphn×n
And step 3: extracting features of graph data by adopting a graph convolutional neural network, and representing the last hidden layer by a softmax function to obtain a final graph representation;
step 4, defining an objective function L for detecting the community structure by using the modularity matrixcomTo obtain global information and combine it with a cross entropy loss function L for node classificationcroMerge into a unified loss function Lc
Step 5. optimization of parameters using back-propagation algorithm, minimizing loss function LcUntil it converges, represented by the iterated update map.
Compared with the prior art, the invention has the beneficial effects that:
the invention can simultaneously obtain the local and global structure information of the graph to learn graph representation, provides a community-enhanced graph convolution neural network method, unifies the extraction of the local and global information into a network model by defining a new loss function, solves the problem that the global structure information is neglected, and improves the learning and representation capability of graph data.
Drawings
FIG. 1 is a general frame diagram, namely an abstract figure;
FIG. 2 is a schematic diagram of a community enhanced graph convolution neural network;
FIG. 3 is a visualization result graph;
FIG. 4 data set parameters;
FIG. 5 semi-supervised classification results;
FIG. 6 shows the node clustering result.
Detailed Description
The present invention will be described in further detail with reference to specific embodiments. FIG. 1 shows a flow chart of the community enhanced convolutional neural network learning algorithm of the present invention. As shown in fig. 1, a community-enhanced convolutional neural network learning algorithm of the present invention includes:
1. inputting a feature matrix formed by node feature vectors of graph data and an adjacency matrix of a graph;
2. calculating a modularity matrix of the graph;
3. extracting features of the graph data by adopting a graph convolutional neural network, and obtaining a final graph representation by the last layer of hidden representation through a softmax function;
4. defining a target function for detecting a community structure and fusing the target function and a cross entropy function into a unified loss function;
5. parameters are optimized, and a loss function is minimized, so that the graph is represented by an iteration updating graph.
The following describes a specific implementation process of the technical solution of the present invention with reference to the accompanying drawings.
1. Data set
The invention utilizes three standard citation network data sets, including Cora, Citeseer and Pubmed data sets, as shown in fig. 4, and counts the parameters of each data set. In these datasets, nodes correspond to documents, edges correspond to inter-referenced relationships between documents, and edges and nodes are connected undirectly. The node is characterized by an element represented by a word bag model of the document corresponding to the node, and the label of the node is the research field related to the document. In the experiment, only 20 nodes from each type of data are selected for training the model, and the performance of label prediction on 1000 test nodes is evaluated.
2. Community-enhanced graph convolution neural network method
2.1 graph data definition
The invention is represented by G ═ V, E, where V represents the set of vertices and E represents the set of edgesn×mThe adjacency matrix is denoted A ∈ Rn×nN represents the number of nodes and m represents the number of features.
2.2 calculation of the modularity matrix
Calculating a modularity matrix B ∈ R of the input diagramn×nThe calculation formula of the elements in the matrix is as follows:
Figure BSA0000197527710000021
wherein A isijIs an element of the adjacency matrix, kiIs the degree of the ith node and e is the number of edges.
2.3 local feature acquisition
Local feature extraction is carried out by adopting a graph convolutional neural network method to obtain hidden layer representation of a graph:
Figure BSA0000197527710000022
wherein,
Figure BSA0000197527710000023
i is the identity matrix. σ (-) denotes an activation function, W(l)Is the weight matrix that needs training learning, and l is the number of layers. The hidden layer of the last layer is represented as H(L)And (3) transmitting to a softmax function to obtain a final graph representation, namely the prediction of the label:
Z=soft max(H(L)) (3)
using the cross entropy loss function as an objective function for node classification:
Figure BSA0000197527710000031
where i ∈L is the node index set with labels, K is the number of node categories, and YA corresponding label indication representing the ith marker node.
2.4 acquisition of Global information
Introducing a community structure into a network to obtain global information of the graph, wherein modularity is an index for measuring the strength of the community structure, and an objective function for detecting the community structure is defined by using a modularity matrix:
Figure BSA0000197527710000032
combining the two objective functions to obtain a final loss function as follows:
Lc=Lce-αLcom(6)
wherein α is a hyper-parameter that controls community structure effects.
2.5 optimization of parameters
Iteratively updating neural network weights based on training data to optimize parameters using a back-propagated Adam algorithm, minimizing a loss function LcUntil it converges, the graph is represented with an iteratively updated graph.
3. Model parameter setting
The nonlinear activation function adopts a Re L U function, the number of hidden layers of the model is 2, dropout is 0.5, L2 regularization parameter is 5 & 10-4The number of hidden layer units is 32, the learning rate is 0.01, the number of training iterations is 200, and the settings of α under the Cora, cieseer, and Pubmed data sets are 1.2, 1.5, and 1, respectively.
4. Comparison algorithm
The method of the invention was compared in experiments with the following method:
ManiReg: the model is a semi-supervised learning model based on manifold regularization, and can fully utilize the geometric characteristics of edge distribution;
semi Emb: is a semi-supervised embedded learning model;
l P, a Label propagation method based on a Gaussian random field model;
deepwalk: deep walking, which is a graph network embedding method based on random walking;
Planetoid-T: an inductive, embedding-based semi-supervised learning model;
ChebNet: the method is a spectrogram convolution neural network, and reduces calculation of Laplace eigenvectors and generation of a spatial localization filter by performing Chebyshev expansion on the graph Laplace;
GCN: a classical atlas neural network adopts a first-order approximate spectral filter, and provides a simplified model for semi-supervised learning.
And (3) GAT: an improved method of graph convolution neural networks employs an attention mechanism to assign different weights to the neighbors of a node when aggregating feature information.
5. Results of the experiment
Fig. 5 shows the performance of the semi-supervised classification task performed in three data sets by the present invention, with evaluation indexes of accuracy and F1 score. The algorithm with the best classification effect can be known as CE-GCN by observing the table, namely the method. Fig. 6 shows the performance of clustering tasks performed in three data sets, and the experiment performed clustering using KMeans algorithm, and the input dimension was consistently set to 64 to compare the performance of different methods. From the data, it can be seen that the CE-GCN still maintains significant advantages over other methods. In addition, fig. 3 shows a comparison result when performing a data visualization task. Experimental results show that the method has better representation capability than the existing algorithm on tasks related to the graph nodes.
The foregoing examples are merely illustrative of the principles and efficacy of the present invention and are not intended to limit the scope of the invention, it being understood that the invention is not limited to the implementations described herein, which are described for the purpose of assisting those skilled in the art in practicing the invention. Modifications and improvements to the above-described embodiments may occur to those skilled in the art without departing from the spirit and scope of the invention, and it is intended that the invention be limited only by the appended claims.

Claims (8)

1. A community-enhanced graph convolution neural network method, comprising the steps of:
step 1: inputting a feature matrix formed by node feature vectors of graph data and an adjacency matrix of a graph;
step 2: calculating a modularity matrix of the graph;
and step 3: extracting features of the graph data by adopting a graph convolutional neural network, and obtaining a final graph representation by the last layer of hidden representation through a softmax function;
and 4, step 4: defining a target function for detecting the community structure by using the modularity matrix and fusing the target function and the cross entropy function into a unified loss function;
and 5: parameters are optimized, and a loss function is minimized, so that the graph is represented by an iteration updating graph.
2. The method of claim 1, wherein in step 1, a node feature matrix X ∈ R is obtainedn×mAnd adjacency matrix A ∈ Rn×nAs inputs, n represents the number of nodes and m represents the number of features.
3. The method of claim 1, wherein in step 2, a modularity matrix B ∈ R of the graph is calculatedn×nAnd providing data preparation for information acquisition of community structures.
4. The method of claim 1, wherein in step 3, a graph convolution neural network method is used to perform feature extraction layer by layer, new node representations are obtained by fusing neighbor information of nodes, and representations of graph data obtained by convolution layers are called hidden layer representations.
5. The method of claim 1, wherein in step 3, the last hidden layer representation is transferred to a softmax perception layer to obtain a final graph representation Z.
6. The method of claim 1, wherein in step 4, modularity is introduced into the network to measure the strength of the community structure, and the objective function L for detecting the community structure is defined by a matrix of the modularitycomTo obtain global information of the graph.
7. The method of claim 1, wherein in step 4, a cross-entropy loss function L is usedcroAs an objective function for node classification, the objective function L for global information extraction is usedcomAre fused into a unified loss function Lc
8. The method of claim 1, wherein in step 5, the loss function L is minimized by using back-propagation algorithm to optimize parameterscUntil it converges, and then iteratively updates the graph representation.
CN201911288719.9A 2019-12-16 2019-12-16 Community-enhanced graph convolution neural network method Pending CN111476261A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201911288719.9A CN111476261A (en) 2019-12-16 2019-12-16 Community-enhanced graph convolution neural network method

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201911288719.9A CN111476261A (en) 2019-12-16 2019-12-16 Community-enhanced graph convolution neural network method

Publications (1)

Publication Number Publication Date
CN111476261A true CN111476261A (en) 2020-07-31

Family

ID=71746181

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201911288719.9A Pending CN111476261A (en) 2019-12-16 2019-12-16 Community-enhanced graph convolution neural network method

Country Status (1)

Country Link
CN (1) CN111476261A (en)

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112183234A (en) * 2020-09-10 2021-01-05 北京华跃信息技术有限公司 Situation perception method and device based on graph neural network
CN112925909A (en) * 2021-02-24 2021-06-08 中国科学院地理科学与资源研究所 Graph convolution document classification method and system considering local invariance constraint
CN113114677A (en) * 2021-04-13 2021-07-13 中国互联网络信息中心 Botnet detection method and device
CN113269647A (en) * 2021-06-08 2021-08-17 上海交通大学 Graph-based transaction abnormity associated user detection method
CN113627463A (en) * 2021-06-24 2021-11-09 浙江师范大学 Citation network diagram representation learning system and method based on multi-view comparison learning
WO2022252455A1 (en) * 2021-06-01 2022-12-08 Huawei Technologies Co., Ltd. Methods and systems for training graph neural network using supervised contrastive learning
CN116308856A (en) * 2023-02-10 2023-06-23 华南师范大学 Community discovery method and device oriented to multi-layer learner relationship network
CN116563049A (en) * 2023-04-24 2023-08-08 华南师范大学 Directed weighted symbol social network community discovery method

Cited By (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112183234A (en) * 2020-09-10 2021-01-05 北京华跃信息技术有限公司 Situation perception method and device based on graph neural network
CN112925909A (en) * 2021-02-24 2021-06-08 中国科学院地理科学与资源研究所 Graph convolution document classification method and system considering local invariance constraint
CN113114677A (en) * 2021-04-13 2021-07-13 中国互联网络信息中心 Botnet detection method and device
CN113114677B (en) * 2021-04-13 2022-09-27 中国互联网络信息中心 Botnet detection method and device
WO2022252455A1 (en) * 2021-06-01 2022-12-08 Huawei Technologies Co., Ltd. Methods and systems for training graph neural network using supervised contrastive learning
CN113269647A (en) * 2021-06-08 2021-08-17 上海交通大学 Graph-based transaction abnormity associated user detection method
CN113269647B (en) * 2021-06-08 2022-11-18 上海交通大学 Graph-based transaction abnormity associated user detection method
CN113627463A (en) * 2021-06-24 2021-11-09 浙江师范大学 Citation network diagram representation learning system and method based on multi-view comparison learning
CN116308856A (en) * 2023-02-10 2023-06-23 华南师范大学 Community discovery method and device oriented to multi-layer learner relationship network
CN116563049A (en) * 2023-04-24 2023-08-08 华南师范大学 Directed weighted symbol social network community discovery method
CN116563049B (en) * 2023-04-24 2024-10-18 华南师范大学 Directed weighted symbol social network community discovery method

Similar Documents

Publication Publication Date Title
CN111476261A (en) Community-enhanced graph convolution neural network method
Ding et al. Self-supervised locality preserving low-pass graph convolutional embedding for large-scale hyperspectral image clustering
CN112925989B (en) Group discovery method and system of attribute network
CN110728224B (en) Remote sensing image classification method based on attention mechanism depth Contourlet network
CN109977232B (en) Graph neural network visual analysis method based on force guide graph
CN103839261B (en) SAR image segmentation method based on decomposition evolution multi-objective optimization and FCM
Sharma et al. Classification through machine learning technique: C4. 5 algorithm based on various entropies
CN113010691A (en) Knowledge graph inference relation prediction method based on graph neural network
CN107562812A (en) A kind of cross-module state similarity-based learning method based on the modeling of modality-specific semantic space
CN104217214A (en) Configurable convolutional neural network based red green blue-distance (RGB-D) figure behavior identification method
Miranda et al. A hybrid meta-learning architecture for multi-objective optimization of SVM parameters
CN103489033A (en) Incremental type learning method integrating self-organizing mapping and probability neural network
Özbılge et al. Tomato disease recognition using a compact convolutional neural network
CN113157957A (en) Attribute graph document clustering method based on graph convolution neural network
CN117524353B (en) Molecular large model based on multidimensional molecular information, construction method and application
Xie et al. CNN and KPCA-based automated feature extraction for real time driving pattern recognition
CN115544239A (en) Deep learning model-based layout preference prediction method
CN113989544A (en) Group discovery method based on deep map convolution network
Zhang et al. Protein family classification with multi-layer graph convolutional networks
CN109784404A (en) A kind of the multi-tag classification prototype system and method for fusion tag information
Zhao et al. A pipeline for fair comparison of graph neural networks in node classification tasks
CN115273645B (en) Map making method for automatically clustering indoor surface elements
CN112465253B (en) Method and device for predicting links in urban road network
CN115346055A (en) Multi-kernel width map based neural network feature extraction and classification method
Fan et al. Gated graph pooling with self-loop for graph classification

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
RJ01 Rejection of invention patent application after publication

Application publication date: 20200731

RJ01 Rejection of invention patent application after publication