Abstract
Graph Neural Networks (GNNs) are gaining increasing attention on graph data learning tasks in recent years. However, in many applications, graph may be coming in an incomplete form where attributes of graph nodes are partially unknown/missing. Existing GNNs are generally designed on complete graphs which can not deal with attribute-incomplete graph data directly. To address this problem, we develop a novel partial aggregation based GNNs, named Partial Graph Neural Networks (PaGNNs), for attribute-incomplete graph representation and learning. Our work is motivated by the observation that the neighborhood aggregation function in standard GNNs can be equivalently viewed as the neighborhood reconstruction formulation. Based on it, we define two novel partial aggregation (reconstruction) functions on incomplete graph and derive PaGNNs for incomplete graph data learning. Extensive experiments on several datasets demonstrate the effectiveness and efficiency of the proposed PaGNNs.
Introduction
In real-world applications, graph data—such as social networks or biological systems—is frequently "incomplete." Node attributes may be missing due to privacy restrictions, sensor failures, or errors during data collection. Standard Graph Neural Networks (GNNs) typically assume complete datasets and struggle when faced with missing values. Conventional solutions often rely on two-stage imputation (using separate models like GANs to fill gaps) or complex probabilistic frameworks. These approaches are often computationally expensive and may not be optimized for the final downstream task. This paper introduces Partial Graph Neural Networks (PaGNNs), a framework designed to learn directly from incomplete graph data by redefining neighborhood aggregation.
Methodology
The core innovation of PaGNN is the re-interpretation of neighborhood aggregation as a neighborhood reconstruction problem. In a standard GNN, a node representation is updated by summarizing information from its neighbors. Mathematically, this can be viewed as finding a representation that minimizes the distance (Frobenius norm) between a node and its neighborhood.
The Partial Aggregation Scheme
To handle missing data, the authors introduce an indicative matrix ($M$). This binary mask identifies known attributes (1) and missing ones (0). By integrating this mask into the aggregation step using Hadamard (element-wise) products, the network can propagate only known information, effectively ignoring missing dimensions without requiring explicit imputation.
Two primary variants are proposed:
- PaGNN-M: Utilizes a weighted mean aggregation.
- PaGNN-N: Employs a symmetric normalized aggregation, mirroring the popular Graph Convolutional Network (GCN) architecture.
Experimental Setup
The models were evaluated on four benchmark datasets: Cora, Citeseer, AmaPhoto, and AmaComp. The authors simulated two types of incompleteness:
- Type 1: Entire nodes are missing all attributes.
- Type 2: Individual elements within attribute vectors are missing at random.
Missing rates were tested from 10% to 90% to assess the robustness of the proposed architecture against varying levels of data sparsity.
Key Results and Discussion
PaGNN-N consistently outperformed competitive baselines, including GAN-based methods (GAIN) and probabilistic models (GCNMF). Notably, the model maintained high accuracy even when 90% of attributes were missing, suggesting that the graph's structural information can significantly compensate for missing features.
Efficiency and Convergence
Unlike models that require complex estimation of missing values, PaGNN maintains the computational complexity of a standard GCN ($O(E)$). In empirical tests, it achieved speedups of 10x to 20x per epoch compared to GCNMF and SAT. Furthermore, training loss curves indicate that both PaGNN variants converge quickly and smoothly, even under high missing-data regimes.
Conclusion
PaGNNs provide a mathematically grounded and efficient solution for learning on incomplete graphs. By treating aggregation as a partial reconstruction task, the model avoids the overhead of separate imputation stages while achieving state-of-the-art performance. Future work may explore the application of PaGNNs to dynamic graphs and scenarios where data is "Missing Not At Random" (MNAR), further expanding its utility in complex real-world environments.
Summary updated