Source-linked AI summary
Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, Jianzhu Ma
TL;DR
GNN performance is limited by heterogeneous mixing patterns that global assortativity does not adequately represent. The paper uses local assortativity to analyze this limitation and builds a computation graph combining proximity with multiscale structural information. Experiments report improved assortativity and GNN performance when models adaptively use structure and proximity across diverse real-world graphs.
Problem
Global assortativity can miss heterogeneous local mixing, while GNN performance is associated with node-level assortativity and is weaker for disassortative nodes.
Method
The paper transforms each input graph into a multi-relational computation graph encoding original proximity and structural similarity from multiscale degree sequences.
Results
Across real-world networks, the transformed computation graph experimentally improves assortativity and GNN performance, with adaptive use of structure and proximity increasing performance across local-assortativity regimes.
Takeaways & Limitations
GNNs can benefit from running on a transformed computation graph that adaptively chooses between proximity and structural information under diverse mixing.
Takeaways & Limitations
The analysis assumes features and class labels are correlated when explaining why disassortative nodes have nonsmooth neighborhoods.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) have achieved tremendous success on multiple graph-based learning tasks by fusing network structure and node features. Modern GNN models are built upon iterative aggregation of neighbor's/proximity features by message passing. Its prediction performance has been shown to be strongly bounded by assortative mixing in the graph, a key property wherein nodes with similar attributes mix/connect with each other. We observe that real world networks exhibit heterogeneous or diverse mixing patterns and the conventional global measurement of assortativity, such as global assortativity coefficient, may not be a representative statistic in quantifying this mixing. We adopt a generalized concept, node-level assortativity, one that is based at the node level to better represent the diverse patterns and accurately quantify the learnability of GNNs. We find that the prediction performance of a wide range of GNN models is highly correlated with the node level assortativity. To break this limit, in this work, we focus on transforming the input graph into a computation graph which contains both proximity and structural information as distinct type of edges. The resulted multi-relational graph has an enhanced level of assortativity and, more importantly, preserves rich information from the original graph. We then propose to run GNNs on this computation graph and show that adaptively choosing between structure and proximity leads to improved performance under diverse mixing. Empirically, we show the benefits of adopting our transformation framework for semi-supervised node classification task on a variety of real world graph learning benchmarks.
1 INTRODUCTION
GNNs aggregate neighborhood information under an assortative-mixing assumption, but real-world graphs often contain heterogeneous local mixing patterns. The paper studies local assortativity and transforms graphs to combine proximity with structural information.
- GNNs and mixing patterns: GNN message passing propagates and aggregates neighboring features, effectively performing neighborhood smoothing for downstream prediction.This approach assumes nearby nodes tend to have similar attributes or labels.
- Heterogeneous mixing: Global assortativity statistics are informative mainly when a network’s mixing patterns are concentrated around a common mean.Real-world graphs may instead contain assortative and disassortative regions.
- Structural similarity: Disassortative nodes can share structural features with distant nodes even when their immediate neighborhoods have different labels.The paper illustrates this using nodes with similar multihop degree patterns but dissimilar local neighborhoods.
- Proposed direction: The paper measures mixing with node-centric local assortativity, relates it to GNN representation capability, and transforms graphs using proximity and local structural similarity.The transformed computation graph is designed for running GNNs with both information types.
2 PRELIMINARIES
The preliminaries define graphs, node features, neighborhoods, semi-supervised node classification, message passing, and global assortativity. These concepts establish the notation and baseline measurement used later.
- Graph notation: A graph G = (V, E) consists of nodes V and edges E, with adjacency matrix A representing edge existence or weights.Node features are represented by a matrix X, and each node has a feature vector.
- Node classification: The neighborhood N(u) contains nodes exactly one hop from u, and semi-supervised node classification learns labels from some labeled nodes.The task learns a function mapping nodes to class labels.
- Message passing: Neural message passing repeatedly sends vector messages across edges and updates node representations for K rounds.The parameters are learned through a loss function and backpropagation.
- Global assortativity: Global assortativity summarizes how similarly labeled or attributed nodes mix across the entire network.Its formulation uses mixing quantities associated with attribute groups and edge endpoints.
3 RELATED WORK
Related work characterizes GNNs as local smoothing methods and identifies limitations from neighborhood-local operations. Existing approaches add diffusion, geometric, multihop, or attention-based graph information.
- Positioning: The paper positions its approach among methods that enrich GNN inputs with information beyond ordinary local message passing.Its specific focus is on proximity and structural equivalence under diverse mixing patterns.
- Limits of local message passing: GNN convolution operations are local, limiting direct access to higher-order graph information.Stacking layers can introduce over-smoothing, making node representations indistinguishable.
- Attention-based methods: Graph attention adaptively selects relevant neighborhood information but still performs smoothing over surrounding nodes.This preserves the local aggregation paradigm while changing its weighting.
- Alternative graph information: Prior methods supplement or replace basic message passing with PageRank, graph diffusion, geometric aggregation, signed hop weights, or jumping connections.These approaches incorporate information beyond a single standard neighborhood aggregation pattern.
4 GNNS AND LOCAL MIXING
The paper replaces global mixing summaries with node-level local assortativity to analyze GNN behavior under diverse mixing. Across real-world graphs, local assortativity varies widely and GNN performance tracks it, especially failing for disassortative nodes.
- Local assortativity: Global assortativity can obscure diverse local mixing because it averages edge mixing across the whole network.Local assortativity instead weights edges according to their locality around a node.
- Local assortativity: Personalized PageRank provides the locality weighting for node-level assortativity, with α interpolating from a trivial neighborhood to global assortativity.At α = 1, the local measure recovers the global assortativity metric.
- Empirical mixing patterns: Skewed and multimodal local-assortativity distributions occur across many networks even when global assortativity is approximately zero.This indicates that the global coefficient does not provide a complete picture of network mixing.
- GNN performance: GNN performance is highly correlated with node-level local assortativity across tested real-world graphs.Most evaluated GNNs perform poorly for nodes with r_local(l) < 0 because neighborhood features differ substantially from the target node’s features.
- GNN performance: Disassortative neighborhoods tend to have low label smoothness and high feature dissimilarity, whereas assortative neighborhoods provide smoother signals for GNNs.The paper summarizes this relationship as ε_u ∝ 1/λ_u.
5 OUR FRAMEWORK
The framework transforms the original graph into a weighted multi-relational computation graph that preserves proximity while encoding structural equivalences at multiple neighborhood hierarchies. GNNs then perform relation-aware message passing with edge weights and attention to adaptively use structural and proximity information.
- Computation graph: The computation graph preserves the original nodes and encodes both proximity information and structural equivalences from the input graph.It is constructed without class labels and is intended to retain proximity while adding model-free structural information.
- Structural relations: Structural similarity is estimated by comparing ordered degree sequences across progressively larger neighborhood hierarchies using recursively defined structural distances.Fast Dynamic Time Warping compares sequences of different sizes, while the recursive distance remains nondecreasing across hops.
- Edge construction: The construction creates T + 1 structural edge types alongside one proximity edge type, with structural edge weights varying inversely with structural distance.Structural weights are larger when nodes have similar network structure, while original graph edges are added with weight one.
- Scalability: Practical construction restricts each node’s structural-similarity calculations to O(log n) candidates per hop, yielding O(nlogn) edges for each structural relation instead of O(n^2).The unrestricted construction can introduce at most E + (T + 1)(n^2) edges.
- Model variants: WRGNN models apply the transformed computation graph to semi-supervised node classification, with WRGAT and WRGCN selected for experimental analysis.The framework is designed for K-layer message passing on the multi-relational computation graph.
- Message passing: Relation-aware message passing assigns a transformation matrix to each edge type and uses type-specific weights and attention coefficients to combine structural and proximity information.The framework is instantiated as WRGNN, with WRGAT and WRGCN variants differing in whether attention is used.
6 EXPERIMENTS AND RESULTS
The framework is evaluated for semi-supervised node classification across diverse real-world networks, using a computation graph that combines proximity and structural information. Results show that transformation increases local assortativity and that adaptively combining information improves performance across mixing regimes.
- Experimental setup: The evaluation covers semi-supervised node classification on hyperlinked web, citation, air traffic, and BGP networks using accuracy and F1-Micro metrics.The compared methods primarily use message-passing GNN backbones, with reported results based on specified train, validation, and test splits.
- Local assortativity distribution shift: The transformed computation graph shifts previously disassortative nodes toward more assortative local mixing than in the original graph.This supports capturing similar structural regularities between nodes through the transformed graph.
- Node classification performance: On hyperlinked web networks, the framework performs consistently well, while on predominantly assortative citation networks it achieves performance comparable to baselines.The authors attribute the web-network results to structural regularities captured by the computation graph.
- Node classification performance: On air traffic and BGP networks, the framework achieves strong performance compared with other GNN baselines, including settings where baseline GNNs perform poorly without node attributes.Table 2 reports node-classification comparisons for multiple air traffic networks and the BGP network.
- Sensitivity analysis: Adding structural relations improves validation performance over proximity-only baselines on disassortative networks, whereas structure alone is not useful on highly assortative networks.The sensitivity analysis varies the number of structural relations used in the computation graph.
- Ablation analysis: Ablations show that structure-only information helps on predominantly disassortative networks, while attention-based models using both structure and proximity perform best across the evaluated regimes.For highly assortative networks, structure-only information hurts relative to the proximity baseline, but adaptive combinations yield the best gains.
7 CONCLUSION
The paper uses local mixing patterns to study GNN predictive limitations and develops a graph transformation that improves assortativity and performance by incorporating structural regularities.
- Local mixing patterns provide a perspective for studying GNN predictive performance and limitations.
- The graph transformation improves assortativity by using structural regularities in the input graph.
- Experiments across real-world networks support running GNNs on transformed computation graphs that adaptively choose structure and proximity information.
A BACKGROUND
Neural message passing repeatedly aggregates neighborhood information to update node representations, which are then decoded for node classification.
- During each iteration, a node’s hidden representation is updated using information from its neighborhood.
- AGGREGATE maps neighboring hidden representations to a message vector, while UPDATE combines that message with the node’s current representation.
- Initial representations use original node features, and final representations after K iterations are decoded into class labels.
B APPLYING GNN ON COMPUTATION GRAPH
The section presents the procedure and neighborhood inputs used for node classification on the computation graph.
- Node classification is implemented with an algorithmic procedure for processing node features and graph neighborhoods.
- The computation graph supplies node features and a 1-hop relation-specific neighborhood function.
C DATASET
The evaluation uses diverse real-world graph datasets from multiple domains, with documented node meanings, labels, edges, and features; the structural-similarity search is heuristically reduced in practice.
- The benchmark collection spans Wikipedia, actor co-occurrence, and university web-page networks with task-specific labels and bag-of-words features.
- Naively computing all structural similarities requires O(n^2) calculations, while the practical heuristic achieves O(nlogn).The heuristic limits comparisons using degree differences and a budget of O(logn) candidate nodes per node.
E COMPARISON AGAINST STRUCTURE AWARE GNNS
The paper compares its graph-transformation-plus-GNN approach with DEMO-Net under the same 33% train/validation/test split and reports superior node-classification performance. It also argues that arbitrary-hop degree comparisons provide a more efficient way to improve graph assortativity than conventional structure-aware message passing.
- Experimental comparison: The evaluation reruns DEMO-Net with a 33% train/validation/test split for a fair comparison against the proposed approach.The authors use the exact split and setup associated with DEMO-Net rather than their usual 80/10/10 split.
- Experimental comparison: The graph transformation followed by GNN approach outperforms the structure-aware DEMO-Net baseline in node classification accuracy.Table 4 reports node-classification accuracy as mean ± standard variance under the matched split.
- Method comparison: DEMO-Net’s degree comparisons are usually limited to 2–3 hops because going farther can cause over-smoothing.The paper characterizes DEMO-Net as architecturally similar to GIN while emphasizing this practical limitation on degree-based message passing.
- Method comparison: The proposed graph transformation explicitly compares degrees at arbitrary hops to improve graph assortativity more efficiently.The transformation constructs a computation graph using structural relations in addition to the original graph information.
F HYPER-PARAMETER SETTING
The experiments optimize WRGNN variants with Adam across specified learning-rate and weight-decay ranges, using two-layer architectures and selected nonlinearities.
- Optimizer settings: The experiments use Adam with learning rates {1e-2, 1e-3} and weight decays {0, 1e-5, 5e-4, 5e-6}.These values define the optimizer hyperparameter sweep.
- Architecture settings: WRGNN variants contain two layers followed by a fully connected MLPθ, with ReLU activation for WRGNN and LeakyReLU for WRGAT.The WRGAT negative input slope is 0.2.
- Architecture settings: Hidden dimensions are swept over {16, 32, 64, 128} for WRGNN layers and {32, 64, 128} for the final component.The passage specifies the searched hidden-dimension ranges.