Inductive Neural Operators Learning On Graphs

Graph is a powerful tool for modeling interrelated things.Graph structure data is ubiquitous,such as social networks,scientific research cooperation networks,knowledge graphs,etc.The mining of graph data has always been the main research interests for computer scientists,mathematicians,physicists,biologists,etc.With the increasingly extensive and in-depth application of deep learning on graph data,we have built a novel and powerful inductive neural operator learning framework on graphs.By transforming the problem of graph mining into an inductive operator learning problem on a graph,many original difficult problems can be addressed effectively.Specifically,we did the following:(1)We established an inductive neural operator GRAINO learning framework on the graph based on ‘encoding-decoding'.The encoder is generally designed as a multi-layer GNN structure,which encodes the graph information in the low-dimensional vector space,and each node or subgraph is represented as a set of vectors? the decoder is directly related to the task.The operator can be totally trained on small scale synthetic graphs,and then tested on larger size ones.(2)We designed the operator GPT-GNN for pre-training the general graph neural networks.A major limitation of current graph neural network applications is that suffi-cient training often requires a large amount of labels and domain-specific input features.GPT-GNN designed the encoder as the multi-layer GNNs,and set up three self-supervised tasks for training to enable GPT-GNN to capture the graph structure from different gran-ularities.We used the DCBM model to generate synthetic training graphs with different structural characteristics.Through the extensive training,the operator enables the encoder(i.e.,the pre-trained GNN model)to extract the general graph structural features,thereby providing good feature inputs for downstream tasks.The results of the classification tasks from node level,link level to graph level on real networks all show the effectiveness of GPT-GNN in pre-training GNNs?(3)We designed the operator Dr BC to identify high betweenness nodes on large graphs.We for the first time turn the problem of esitimating betweenness into a learning problem,and designed the encoder and decoder specifically.The encoder is designed as a multi-layer GNN model,which encodes nodes as a set of low-dimensional vectors,es-sential structural information on BC calculations is embeded into the vector? the decoder is designed as a multi-layer perceptron,which decodes the node vectors to scalar values that estimate its BC ranking score.The operator can be trained on small PLC graphs and tested on larger size instances and real-world networks.Extensive results showed Dr BC can greatly speed up BC calculations while sacrifice little accuracy,which turns to be a feasible choice for rapid return of those high BC nodes on large graphs.Besides,as the first success of GNN in BC calculations,Dr BC tells us to what extent can GNN capture the graph structures and how?(4)We designed the operator FINDER for optimal attacks of graphs.The optimal attack problem of graphs is a well-known NP-hard combinatorial optimization problem on graphs.We for the first time explored this problem from the learning perspective.Based on the 'encode-decode' structure of GRAINO,FINDER designed the encoder as a multi-layer GNN model,and encodes nodes and subgraphs as vectors to represent actions(nodes)and states(subgraphs)? The neural tensor network decodes the action and the state vector into the scalar values to represent the action's long-term gains.We used Q learning to train and update the parameters.Similarly,the operator can be trained on small-scale BA graphs,and tested on large-scale real networks.The experimental results show that FINDER beats the best existing results in both effectiveness and efficiency.More importantly,FINDER itself is also very versatile,one only needs to modify the reward function to adapt to a large class of graph attack problems.Our work is the development and application of deep learning in the field of graph data,which provides a novel,general and effective tool for graph data mining.