Source-linked AI summary
Node Similarity Preserving Graph Convolutional Networks
Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, Jiliang Tang
TL;DR
GCN neighborhood aggregation can destroy original node similarity, especially when graph structure is unreliable. SimP-GCN adaptively combines structural and feature information and uses self-supervised similarity learning; experiments report stronger performance than representative baselines across assortative and disassortative graphs.
Problem
GCN aggregation can destroy node similarity in the original feature space, which matters when graph structure is unreliable or node similarity is important.
Method
SimP-GCN adaptively integrates graph structure and node features during aggregation and uses self-supervised learning to capture pairwise similarity and dissimilarity.
Results
SimP-GCN outperforms representative baselines across assortative and disassortative graphs and preserves more feature-similarity information.
Takeaways & Limitations
Preserving node similarity while using graph structure provides a basis for effective graph convolution across varied graph structures.
Takeaways & Limitations
Naive pairwise feature-similarity computation has O(n^2) time complexity, although parallel and approximate methods can reduce the cost.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs) have achieved tremendous success in various real-world applications due to their strong ability in graph representation learning. GNNs explore the graph structure and node features by aggregating and transforming information within node neighborhoods. However, through theoretical and empirical analysis, we reveal that the aggregation process of GNNs tends to destroy node similarity in the original feature space. There are many scenarios where node similarity plays a crucial role. Thus, it has motivated the proposed framework SimP-GCN that can effectively and efficiently preserve node similarity while exploiting graph structure. Specifically, to balance information from graph structure and node features, we propose a feature similarity preserving aggregation which adaptively integrates graph structure and node features. Furthermore, we employ self-supervised learning to explicitly capture the complex feature similarity and dissimilarity relations between nodes. We validate the effectiveness of SimP-GCN on seven benchmark datasets including three assortative and four disassorative graphs. The results demonstrate that SimP-GCN outperforms representative baselines. Further probe shows various advantages of the proposed framework. The implementation of SimP-GCN is available at \url{https://github.com/ChandlerBang/SimP-GCN}.
1 INTRODUCTION
The paper argues that neighborhood aggregation in GNNs can destroy original node feature similarity, motivating SimP-GCN to balance structural and feature information while preserving similarity.
- Motivation: GCNs aggregate and transform neighborhood information, but their smoothing process reduces overall node-feature differences and tends to destroy original similarity.The authors connect graph convolution to Laplacian smoothing theoretically and examine the effect empirically.
- Motivation: Node similarity matters when graph structure is unreliable, including disassortative graphs, adversarially manipulated graphs, low-degree settings, and deep models affected by over-smoothing.Over-smoothing can make learned node embeddings indistinguishable.
- Approach: SimP-GCN adaptively integrates graph structure and node features during aggregation to preserve similarity in a data-driven way.The strategy lets each node adjust the relative information drawn from structure and features.
- Approach: A self-supervised similarity-prediction task explicitly captures pairwise feature similarity and dissimilarity relations from hidden representations.The paper frames similarity prediction as a pretext task for encoding pairwise feature relations.
- Results: SimP-GCN outperforms representative baselines on both assortative and disassortative graphs, while preserving feature similarity and improving robustness against adversarial attacks.The contribution summary reports extensive experimental support for these outcomes.
2 RELATED WORK
Prior GNN research includes spectral and spatial approaches, but graph-based methods can perform poorly when graph structure is noisy or mismatched with node features.
- GNN Approaches: GNNs are broadly organized into spectral-based and spatial-based methods for learning representations on graph-structured data.Spectral methods derive representations from graph spectral theory.
- Structural Limitations: Performance can deteriorate on disassortative graphs because homophily does not hold and graph structure introduces noise.In these settings, structural information may not be optimal for prediction.
- Structural Limitations: Adversarial attacks can inject carefully crafted structural noise that disturbs graph-based models and causes wrong predictions.The paper motivates using original features more carefully when structure is unreliable.
3 PRELIMINARY STUDY
The preliminary study links GCN aggregation to Laplacian smoothing and evaluates whether learned representations retain feature similarity across assortative and disassortative graphs.
- GCN Basics: A graph is represented by nodes, edges, and a node-feature matrix, while adjacency entries indicate whether node pairs are connected.The node-feature matrix contains one feature vector per node.
- GCN Basics: A GCN layer propagates normalized adjacency information through a weight matrix and nonlinearity, with the input representation initialized as H(0) = X.The output H(l) is the representation at layer l.
- Laplacian Smoothing: GCN neighborhood aggregation naturally smooths features and is equivalent to one-step gradient descent on a Laplacian-smoothing signal-recovery objective when c = 1.The smoothing objective favors signals with smaller differences between adjacent nodes.
- Laplacian Smoothing: Because GCN increases similarity between connected nodes, it can destroy original feature similarity and introduce substantial noise on disassortative graphs.The paper explicitly connects this effect to low homophily.
- Empirical Study: The empirical study compares original, feature-based kNN, and GCN-hidden-representation graphs on Cora, Citeseer, Actor, and Cornell using pairwise overlap.The experiment sets k = 3 and measures overlap as the percentage of shared edges.
- Empirical Study: Assortative graphs show greater overlap between structure and features than disassortative graphs, indicating stronger alignment between the two information sources.The comparison follows the reported overlap patterns in Table 1.
4 THE PROPOSED FRAMEWORK
SimP-GCN combines adaptive aggregation with self-supervised learning to preserve node feature similarity while balancing structural and feature information.
- Framework: SimP-GCN has two components: node similarity preserving aggregation and self-supervised learning.The components address balancing graph structure with features and modeling similar and dissimilar node pairs.
- Node Similarity Preserving Aggregation: Its aggregation component adaptively balances graph-structure and node-feature influence during message passing.The strategy is designed to preserve node similarity while using both information sources.
- Self-Supervised Learning: Its self-supervised component considers similar and dissimilar node pairs to better preserve node similarity.This component explicitly addresses pairwise feature relations.
4.1 Node Similarity Preserving Aggregation
SimP-GCN preserves feature similarity by constructing a feature-based kNN graph and adaptively integrating it with the original graph during aggregation. It also lets nodes adjust the contribution of their own features through learnable self-loops.
- Feature Graph Construction: SimP-GCN constructs a kNN graph from cosine similarity between node features and integrates it with the original graph.The feature graph uses each node’s 20 nearest neighbors.
- Adaptive Graph Integration: The propagation process adaptively balances information from the original graph and the feature kNN graph for each node.A node-specific score vector controls the relative influence of the two graphs.
- Adaptive Graph Integration: The score vector is computed from the previous layer’s hidden representations using learnable parameters and a sigmoid activation.This reduces the score-vector parameters from n to d^(l−1) + 1.
- Learnable Self-Loops: Learnable diagonal self-loops allow different nodes to receive different amounts of their own feature information during aggregation.The self-loop contribution is controlled by a predefined hyper-parameter γ.
- Classification Loss: The resulting hidden representations are transformed layer by layer, and the final representation is trained with a classification loss over labeled nodes.The loss compares predictions with true labels using a function such as cross entropy.
4.2 Self-Supervised Learning
SimP-GCN adds self-supervised learning to model pairwise feature similarity more explicitly. Its regression task uses sampled node pairs and hidden representations to capture both similarity and dissimilarity relations.
- Motivation: The feature kNN graph preserves similar node pairs but does not directly push dissimilar nodes apart in the embedding space.Therefore, it does not fully model complex pairwise feature relations.
- Self-Supervised Objective: SimP-GCN introduces a self-supervised contrastive pretext task that assigns constructed labels to node pairs during joint training.The task leverages information from unlabeled nodes.
- Self-Supervised Objective: The self-supervised loss regresses a transformed difference between node representations toward a target similarity value for sampled node pairs.The mapping function is linear, and the target similarity is defined in Eq. (8).
- Implementation: The method uses first-layer hidden representations with l = 1 and sets m = 5 in the regression formulation.The pretext task could alternatively be formulated as classification, but this work adopts regression.
4.3 Objective Function and Complexity Analysis
SimP-GCN jointly optimizes supervised classification and self-supervised losses. Relative to vanilla GCN, its main computational cost is pairwise similarity calculation, while its additional parameters scale linearly with feature dimension.
- Overall Objective Function: The overall objective jointly optimizes the traditional classification loss and the self-supervised loss.A hyper-parameter λ controls the self-supervised loss contribution.
- Time Complexity: Compared with vanilla GCN, the additional computation mainly comes from pairwise feature-similarity calculation for kNN construction and the self-supervised component.The naive time complexity of pairwise similarity calculation is O(n^2).
- Time Complexity: Pairwise similarity computation can be parallelized or accelerated with approximation methods for larger graphs.One cited approach empirically achieves approximate kNN graphs in O(n^1.14).
- Model Complexity: SimP-GCN introduces O(d^(l)) additional parameters compared with GCN, where d^(l) is the input feature dimension at layer l.The additional parameter count is linear in the feature dimension.
5 EXPERIMENT
SimP-GCN is evaluated against representative semi-supervised graph-learning baselines on three assortative and four disassortative graphs. It consistently improves GCN and achieves state-of-the-art results on disassortative graphs, where feature information is especially important.
- Experimental Setup: Experiments cover three assortative citation networks and four disassortative graphs, including Actor, Cornell, Texas, and Wisconsin.The assortative datasets are Cora, Citeseer, and Pubmed.
- Experimental Setup: The evaluation compares SimP-GCN with LP, GCN, kNN-GCN, (A+kNN)-GCN, GAT, JK-Net, and GCNII.These baselines represent structure-only, feature-based, combined-input, attention, multi-range, and residual GNN approaches.
- Assortative Graphs: On three assortative graphs, SimP-GCN consistently improves GCN and achieves the best performance in most settings.The results use average node-classification accuracy over 10 runs.
- Disassortative Graphs: On four disassortative graphs, SimP-GCN consistently improves GCN by a large margin and achieves state-of-the-art results.The reported results average test accuracy over 10 random splits.
- Disassortative Graphs: LP performs extremely poorly on disassortative datasets, while kNN-GCN can outperform several GNN baselines, indicating that feature information is especially important there.Simply combining the original structure and feature-derived graph does not improve kNN-GCN.
5.3 Adversarial Robustness
The adversarial-robustness experiments test SimP-GCN under non-targeted graph attacks across three datasets. SimP-GCN consistently improves GCN, with larger gains as perturbation rates increase.
- Evaluation Setting: The experiments use 10% of nodes for training, 10% for validation, and 80% for testing, averaging accuracy across 10 repetitions.Results under various perturbation rates are shown in Figure 2.
- Results: SimP-GCN consistently improves GCN under different adversarial perturbation rates on all three datasets.The comparison concerns node-classification accuracy under non-targeted metattack.
- Results: Under a 25% perturbation rate on Cora, SimP-GCN achieves over 20% improvement over GCN.The improvement over GCN becomes larger when the perturbation rate is higher.
- Results: SimP-GCN always outperforms GCN-Jaccard, shows comparable performance to Pro-GNN, and achieves the best performance on Citeseer.The observations support robustness under the evaluated adversarial attacks.
5.4 Further Probe
Further probes examine whether SimP-GCN preserves feature similarity, how its adaptive aggregation behaves, and how its components affect performance. The analyses show stronger feature-hidden overlap, node-specific aggregation weights, and contributions from both graph components and self-supervised learning.
- Similarity Preservation: SimP-GCN improves feature-hidden graph overlap on both assortative and disassortative graphs, with roughly 10% improvement on Actor.The measured quantity is OL(A_f, A_h), the overlap between feature and hidden graphs.
- Similarity Preservation: On disassortative graphs, SimP-GCN decreases hidden-original graph overlap because the original structure can be less useful or harmful for downstream tasks.On assortative graphs, both hidden-original and feature-hidden overlaps improve.
- Adaptive Aggregation: On Cora, gamma D(1)_n is extremely small, whereas on Actor and Wisconsin it is much larger, indicating a greater role for original node features in disassortative graphs.The comparison is based on learned values visualized for Cora, Actor, and Wisconsin.
- Ablation Study: Ablation results on disassortative graphs show that A_f and D_n boost performance, while self-supervised learning further improves the model using both components.The study reports average accuracy over 10 runs using the best-performing hyperparameters from Table 4.
6 CONCLUSION
The paper introduces SimP-GCN after showing that GNN aggregation breaks original node similarity. The model adaptively balances structure and feature information while capturing pairwise similarity through self-supervised learning, and outperforms representative baselines across real-world datasets.
- Theoretical and empirical analysis shows that neighborhood aggregation inevitably breaks node similarity in the original feature space.
- SimP-GCN adaptively balances graph-structure and feature information while capturing pairwise node similarity through self-supervised learning.
- Extensive experiments show that SimP-GCN outperforms representative baselines on a wide range of real-world datasets.