Semantic Graph Neural Network with Multi-measure Learning for Semi-supervised Classification

arXiv:2212.01749 · cs.LG · Submitted 2022-12-04 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Semantic Graph Neural Network with Multi-measure Learning for Semi-supervised Classification".

Jane: The gist The proposed framework, Semantic Graph Neural Network with Multi-measure Learning (ML-SGNN),

Tom: First, who's behind it and why it matters.

Paper summary: Tom: We’ve covered that the core idea is moving beyond raw topology by learning optimal graph structures, using semantic graphs to preserve global structure and multi-measure learning to adaptively fuse similarity criteria. Jane, can you summarize the main contribution of this paper in a couple more sentences?

Jane: Well, the thesis is that since raw graph structure is fragile under noise or perturbation, we need comprehensive and robust graph structures for tasks like node classification. The authors propose this Semantic Graph Neural Network with Multi-measure Learning to achieve this by encoding semantic interactions into semantic graphs to capture global context and adaptively fusing multiple similarity measures for better embeddings

Lu: It really boils down to constructing a multi-measure learning method that adaptively fuses multiple measure criteria for a robust graph structure, thereby narrowing the gap between the extracted features and the actual classification performance on page two of THIS PAPER <ref:2212.01749#pg3>

Meng: So if I’m trying to deploy this, am I looking at a complex pipeline with three separate graph embeddings and then an attention layer to fuse them? What’s the complexity there?

Tom: The architecture involves three embeddings: a feature subgraph embedding, an original topology graph embedding, and this new semantic graph embedding. They aggregate these using an attention layer to get the most relevant embedding for classification

Jane: And they build those subgraphs by using different methods. For instance, the feature subgraphs are constructed by multi-measures based on node features and chosen measure functions like Cosine function, Gaussian function, and a novel parameter free similarity measure called Sparsity function

Lu: That Sparsity function is interesting because it involves calculating similarity matrices and then extracting a symmetric sparse adjacency matrix by masking off elements relatively further from node A

Meng: So that’s a lot of different construction happening. What about the semantic graph creation itself? Is that also computationally heavy?

Tom: They generate the semantic graph by randomly sampling a large number of fixed-length sentences in the graph to embed additional semantic information. Then they compute a frequency matrix based on the semantic similarity between pairs of nodes

Jane: Based on that frequency matrix, they define a theta-based embedding layer to preserve the global graph structure, which involves calculating the estimated probability of a node appearing in a context using positive pointwise mutual information or PPMI on page three of THIS PAPER <ref:2212.01749#pg3>

Lu: That PPMI encoding seems like a solid way to inject that semantic information into the original graph structure while keeping track of what's going on globally

Meng: So, to summarize, it’s this complex setup: feature subgraphs from multi-measures, a semantic graph from sentence embeddings and PPMI encoding, and then fusing all three embeddings with an attention layer

Tom: That’s the gist of the ML-SGNN framework. It aims to address the need for comprehensive structure learning rather than just relying on the raw graph data we start with

Jane: And it claims that by optimizing similarity adaptively, they manage to preserve both local and global structure simultaneously for semi-supervised classification tasks

Conclusion: Tom: So wrapping this up on the Semantic Graph Neural Network with Multi-measure Learning for Semi-supervised Classification. The authors are focusing on learning optimal graph structures that go beyond what's just available in the raw data.

Jane: It seems like a pretty sophisticated approach because they’re combining semantic encoding to handle global structure and multi-measure learning to handle similarity adaptation. It’s a detailed framework for building better graph representations

Lu: The authors are emphasizing that the necessity of the semantic graph is what really proves its value, showing that it's essential for capturing the global structure in this kind of semi-supervised setting

Meng: From a practical standpoint, it means we can build more reliable models when labels are scarce because we don't have to rely on perfect topology information for everything

Tom: The results show strong performance improvements across six datasets, with ACC gains as high as three point eight nine percent on BlogCatalog with 20L/C and three point eight percent on UAI2010 with 20L/C

Jane: So, in simple terms, this paper proposes a robust method for semi-supervised classification that learns graph structures by combining semantic context preservation with adaptive similarity evaluation

Lu: It's a good framework because it proves that the need for semantic graph learning and multi-measure learning has a significant impact on preserving global structure of the model embeddings

Meng: For me, it means we can deploy models that are more resilient to messy data structures in real-time traffic scenarios where we can't always guarantee perfect input quality

Tom: Exactly. This work shows that by focusing on robust graph construction and semantic context, we get tangible performance gains without needing a perfect blueprint of the graph structure upfront.

Junchao Lina, Yuan Wana, *, Jingwen Xua, Xingchen Qib

Wuhan University of Technology · The University of Texas at Austin

cs.LG

Submitted: 2022-12-04

Updated: 2022-12-04

Journal ref: Engineering Applications of Artificial Intelligence, Volume 140, 109647, 2025

DOI: 10.1016/j.engappai.2024.109647

Code: https://github.com/phanein/deepwalk

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

The gist: The gist The proposed framework, Semantic Graph Neural Network with Multi-measure Learning (ML-SGNN), learns optimal graph structures by encoding semantic interactions into semantic graphs and

Key concepts

Semantic Graph Learning: This technique generates a new graph based on the meaning (semantics) of nodes. It samples sentences related to nodes and uses information like Positive Pointwise Mutual Information (PPMI) to create an embedding that captures how nodes relate contextually, helping to maintain the overall global structure of the original graph.
Multi-measure Attention Layer: Instead of fixing similarity rules beforehand, this layer adaptively evaluates node similarity by integrating several different measures—such as Cosine, Gaussian, and a novel Sparsity function. This allows the model to dynamically choose the best way to weigh different structural relationships for robust feature learning.
Feature Subgraph Embedding: This embedding represents the local structure of nodes based on their features. It is constructed using multiple feature graphs derived from node features and similarity measures (like Cosine or Gaussian). A graph attention layer is used during merging to reduce hyperparameter dependency when combining these subgraphs.
Module Aggregation Layer: This layer combines three distinct embeddings—feature subgraph, original topology, and semantic graph—using an attention weight. This mechanism determines the most relevant contribution from each structural representation for the final node embedding, ensuring a comprehensive understanding of the graph.

Terminology

GNNs — 3× in this paper · explained in 2 episodes
Downstream Tasks — 2× in this paper · explained in 2 episodes
Ablation — 1× in this paper · explained in 1 episode
Ablation Studies — 1× in this paper · explained in 1 episode
Graph Neural Networks (GNNs) — 1× in this paper · explained in 12 episodes

Summary

The gist The proposed framework, Semantic Graph Neural Network with Multi-measure Learning (ML-SGNN), learns optimal graph structures by encoding semantic interactions into semantic graphs and adaptively fusing multiple similarity measures to preserve both local and global graph structure for semi-supervised classification.

How it works

The model encodes complex interactions in semantics to generate semantic graphs to preserve the global structure of the graph Based on the structural context information of graph and node representations, we encode the complex interactions in semantics and generate semantic graphs to preserve the global structure
A novel multi-measure attention layer is developed to optimize similarity rather than prescribing it a priori, so that the similarity can be adaptively evaluated by integrating measures This mechanism allows for the adaptive fusion of multiple measure criteria for a robust graph structure
The overall architecture involves three embeddings: a feature subgraph embedding, an original topology graph embedding, and a semantic graph embedding These three embeddings are aggregated using an attention layer to obtain the most relevant embedding for classification

Multi-Measure Learning for Local Structure

The method constructs multiple feature graphs based on the node feature matrix and chosen measure functions Three measure functions are chosen to utilize, including Cosine function, Gaussian function, and a novel parameter free similarity measure with steerable sparsity named Sparsity function The process involves calculating similarity matrices and then extracting a symmetric sparse adjacency matrix from them by masking off elements relatively further from node A multi-graph attention layer is introduced when merging multiple subgraphs to reduce the reference of hyper-parameters and ensure the rationality of the model

Semantic Graph Learning for Global Structure

To sufficiently preserve the comprehensive graph structure, a large number of fixed-length sentences are randomly sampled in the graph to embed additional semantic information The frequency matrix is obtained by computing the semantic similarity between pairs of nodes Based on this, a-based embedding layer is defined to preserve the global graph structure This involves calculating the estimated probability of a node appearing in a context using positive pointwise mutual information (PPMI) to encode semantic information in the original graph structure

Module Aggregation and Objective Function

The three embeddings, fea, ori, and sem, are aggregated using a new module aggregation layer where an attention weight agg represents the attention values for nodes to the three graphs The overall objective function combines supervised learning loss with unsupervised constraints to improve generalization The final objective function is defined as  = 0 +  + , where 0 is the classification loss, and  and  are the unsupervised regularizer constraints

Experimental Results

Extensive experiments on six real-world datasets clearly demonstrate the effectiveness of our proposed model and the contribution of each component ML-SGNN performs best on all datasets with all label rates, achieving an improvement of ACC by 3.89% on BlogCatalog with 20L/C and 3.8% on UAI2010 with 20L/C ML-SGNN significantly outperforms all baselines at p < 0.05, which can prove to be a competitive GNN method for semi-supervised classification tasks The performance improvement of ML-SGNN is more prominent compared with the advantages of semantic-based DGCN, particularly on the highly sparse datasets CoraFull where it outperforms the best baseline by 1.92%

Ablation Study Insights

The results show that the semantic graph is effectively capable of preserving the global structure, whereas the other two graphs fail to, which reflects the necessity of semantic graph aggregation in GNN The attention mechanism plays a significant role in balancing the importance of these candidate graphs The ML-SGNN is robust to hyperparameters  and  in a less stringent range of values, which explains the effectiveness of the sparse-inducing 2,1 regularizer constraint The performance improvement relative to parameters  and  approaching 0 when the parameters are within a reasonable range, which explains the effectiveness of the sparse-inducing 2,1 regularizer constraint in Section 3.4.2 The ML-SGNN degenerates into a vanilla GNN model when the semantic graph is ignored, which shows that the semantic graph is effectively capable of preserving the global structure

Conclusion

In this work, we have proposed a framework named MLSGNN for semi-supervised classification tasks It explores the complex interactions in semantics by generating a semantic graph to preserve the global graph structure, and considers the strategy of similarity evaluation by adaptively merging various measures for better embeddings Extensive experiments have shown that our proposed robust semantic graph learning and multi-measure learning have a significant impact on preserving the global structure of the model and node embedding optimization Future work plans to utilize semantic graph learning and multi-measure learning for improving heterogeneous node embedding

Acknowledgements

This work is supported by Excellent Dissertation Cultivation Funds of Wuhan University of Technology under Grant 2021III030JC This work is supported by Excellent Dissertation Cultivation Funds of Wuhan University of Technology under Grant 2021III030JC

References

[1] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, P. S. Yu, A comprehensive survey on graph neural networks, IEEE Transactions on Neural Networks and Learning Systems 32 (2021) 4–24

[5] W. Song, Z. Xiao, Y. Wang, L. Charlin, M. Zhang, J. Tang, Sessionbased social recommendation via dynamic graph attention networks, in: Proceedings of the Twelfth ACM international conference on web search and data mining, 2019, pp. 555–563

[6] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, J. Leskovec, Graph convolutional neural networks for web-scale recommender systems, in: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 974–983

[15] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L Kaiser, I Polosukhin, Attention is all you need, in: Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017

[30] B. Perozzi, R. Al-Rfou, S. Skiena, Deepwalk: Online learning of social representations, in: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014

[33] Q. Li, Z. Han, X. M. Wu, Deeper insights into graph convolutional networks for semi-supervised learning, in: 32nd AAAI Conference on Artificial Intelligence, AAAI 2018

[34] C. Zhuang, Q. Ma, Dual graph convolutional networks for graphbased semi-supervised classification, in: WWW ’18: Proceedings of the 2018 World Wide Web Conference

[38] S. Yun, M.

Improvements for AI systems

Semantic Graph Generation for Global Structure Preservation: The system can encode the complex interactions in semantics and generate semantic graphs to preserve the global structure, which allows node embeddings to be informed by higher-order semantic context beyond local neighborhood aggregation, addressing the challenge that most methods neglect to consider the global graph structure.
Adaptive Multi-Measure Similarity Learning: By utilizing a novel multi-measure attention layer to optimize the similarity rather than prescribing it a priori, so that the similarity can be adaptively evaluated by integrating measures, the system can adaptively fuse multiple measure criteria for a robust graph structure, leading to a more optimal and suitable feature graph to the optimizer for learning the node representation.
Robust Node Representation via Multi-Graph Aggregation: The final node embedding is acquired by aggregating embeddings from three sources—the feature subgraphs constructed by multi-measures, original topology graph, and semantic graph—using an attention layer [agg = Ψagg([fea,sem,ori]), (12)] to obtain the most relevant embedding for supervised learning.
Enhanced Tail Node Embedding Robustness: The framework can improve tail node embeddings during neighborhood aggregation by incorporating the multi-measure feature fusion and semantic context, ensuring the robustness of the tail nodes for better preservation of the global graph structure than DGCN since it considers the optimization of the tail nodes.
Dynamic Measure Weight Adaptation: The system can dynamically learn measure importance through attention weights, as demonstrated by Eq.(4) where the importance of feature subgraph fea is positively related to [attention values], enabling it to adaptively adjust each graph to obtain the best weight, which can avoid the negative impact of data characteristics.