PaperlayerView exact revision on arXiv

Source-linked AI summary

Interpreting and Unifying Graph Neural Networks with An Optimization Framework

Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, Peng Cui

arXiv:2101.11859v1cs.LGcs.SI

TL;DR

GNN research has many propagation mechanisms but limited understanding of their essential relations. This paper unifies representative mechanisms through an optimization framework, develops adjustable low- and high-pass models, and reports stronger benchmark performance with reduced over-smoothing.

  • Problem

    Different GNN propagation mechanisms share message passing patterns, but their essential mathematical relations have received limited analysis.

  • Method

    The paper formulates propagation as optimization with a feature fitting function and graph regularization, then designs adjustable low-pass and high-pass graph kernels.

  • Results

    The proposed GNNs outperform state-of-the-art methods on benchmark datasets and alleviate over-smoothing.

  • Takeaways & Limitations

    The framework provides a macroscopic view for interpreting existing GNNs and a path for deriving new architectures from targeted objective functions.

  • Takeaways & Limitations

    Some analysis simplifies graph convolution by ignoring nonlinear activation and sharing weights across layers.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have received considerable attention on graph-structured data learning for a wide variety of tasks. The well-designed propagation mechanism which has been demonstrated effective is the most fundamental part of GNNs. Although most of GNNs basically follow a message passing manner, litter effort has been made to discover and analyze their essential relations. In this paper, we establish a surprising connection between different propagation mechanisms with a unified optimization problem, showing that despite the proliferation of various GNNs, in fact, their proposed propagation mechanisms are the optimal solution optimizing a feature fitting function over a wide class of graph kernels with a graph regularization term. Our proposed unified optimization framework, summarizing the commonalities between several of the most representative GNNs, not only provides a macroscopic view on surveying the relations between different GNNs, but also further opens up new opportunities for flexibly designing new GNNs. With the proposed framework, we discover that existing works usually utilize naive graph convolutional kernels for feature fitting function, and we further develop two novel objective functions considering adjustable graph kernels showing low-pass or high-pass filtering capabilities respectively. Moreover, we provide the convergence proofs and expressive power comparisons for the proposed models. Extensive experiments on benchmark datasets clearly show that the proposed GNNs not only outperform the state-of-the-art methods but also have good ability to alleviate over-smoothing, and further verify the feasibility for designing GNNs with our unified optimization framework.

1 INTRODUCTION

The paper asks whether diverse GNN propagation mechanisms share a unified mathematical basis and proposes an optimization framework that both explains existing models and guides new designs.

  • Background: The framework targets graph-structured data learning, where GNNs have been applied across recommendation, urban data mining, natural language processing, and computer vision.The paper motivates this broad relevance through the ubiquity of network-structured real-world data.
  • Motivation: GNN propagation mechanisms aggregate node features along network topology, making propagation design central to spatial-based GNNs.Representative mechanisms include attention, personalized pagerank, and jump connections.
  • Unified framework: GCN and PPNP propagation can be summarized as optimizing feature fitting and graph Laplacian regularization terms.The fitting term links propagated representations to original features, while Laplacian regularization smooths features over topology.
  • Novel designs: The framework enables new GNNs to be derived by designing objective functions with adjustable graph convolutional kernels.The paper develops kernels with low-pass and high-pass filtering capabilities.
  • Contributions: The proposed framework theoretically unifies a series of GNN propagation mechanisms and provides a perspective for understanding and designing novel GNNs.It combines an objective optimization formulation with feature fitting and graph regularization.

2 RELATED WORK

Related work distinguishes spectral and spatial GNNs and reviews analyses of their filtering behavior and over-smoothing, while identifying propagation as a central design concern.

  • Graph Neural Networks: Spectral-based GNNs define graph filters in the Fourier domain, whereas spatial-based GNNs design aggregation strategies along network topology.Examples include ChebNet and GWNN for spectral methods and GCN for spatial propagation.
  • Analysis and understanding on GNNs: Prior analyses characterize graph convolution as Laplacian smoothing or a fixed low-pass filter and identify over-smoothing in deep GNNs.These analyses also report that GCN converges toward a random-walk limit distribution as layers increase.
  • Analysis and understanding on GNNs: The paper is situated within research analyzing and understanding GNNs to explain their filtering characteristics and improve their designs.The related work organizes existing theory around spectral filtering and over-smoothing analyses.

3 A UNIFIED OPTIMIZATION FRAMEWORK

The paper models GNN propagation as optimization balancing feature fitting with graph-Laplacian regularization, unifying representative propagation mechanisms. This framework interprets existing models and supports mathematically guided architecture design.

  • Propagation commonalities: GNN propagation combines feature transformation and topology-based aggregation across layers, with topology typically providing smoothing through neighborhood interactions.The framework treats propagated representations as outputs of an optimization process rather than only as message-passing results.
  • Unified objective: The unified objective contains a feature-fitting term for encoding transformed features and a graph-Laplacian regularization term that encourages connected nodes to have similar representations.Graph kernels F1 and F2 determine whether fitting emphasizes all-pass, low-pass, or high-pass information.
  • GNN correspondences: Different propagation mechanisms, including GCN, SGC, PPNP/APPNP, JKNet, and DAGNN, arise as special cases of the unified optimization framework.The paper provides theorem-level correspondences between each propagation mechanism and particular kernel or regularization settings.
  • GCN and SGC: GCN and SGC repeatedly apply normalized adjacency propagation, while their optimization interpretation can reduce to graph regularization under the stated parameterization.The SGC/GCN representation is initialized from transformed features and iteratively propagated through the normalized adjacency matrix.
  • Design implications: The framework enables new GNNs to be derived by selecting objective variables such as graph convolutional kernels and then deriving the corresponding propagation.The authors argue that specifying a targeted objective makes the resulting model more interpretable and reliable.

4 GNN-LF/HF: OUR PROPOSED MODELS

The paper designs low-pass and high-pass GNN objectives by making feature-fitting kernels adjustable, addressing the limitation of forcing all transformed feature information into propagated representations. It also derives closed and iterative low-pass models with convergence guarantees.

  • Motivation: Existing GNN objectives commonly set both fitting kernels to I, requiring all information in H to be encoded into Z even when H contains noise or uncertainty.The paper motivates more flexible kernels because downstream tasks may benefit from low-frequency, high-frequency, or all feature information.
  • Flexible filtering: The proposed framework supports adjustable kernels that selectively encode information from original, low-pass, or other filtering spaces.The balance coefficient μ controls similarity between Z and H across original and low-pass spaces, while α is restricted to ensure positive iterative coefficients.
  • GNN-LF design: GNN-LF uses a low-pass filtering objective and is instantiated in closed-form and iterative propagation variants.The closed form follows from minimizing the objective, whereas the iterative variant avoids constructing a dense matrix inverse.
  • Architecture: The iterative mechanism performs normalized-adjacency neighborhood aggregation with residual connections on H and the filtered feature matrix.Transformation and aggregation are decoupled, following the design pattern used by deep propagation-based GNNs.
  • Convergence: As K→∞, deep GNN-LF-iter converges to GNN-LF-closed and produces the same propagation result.The convergence argument uses a geometric series whose convergence follows from normalized adjacency eigenvalues being bounded in absolute value by 1.

4.2 GNN with High-pass Filtering Kernel

The high-pass filtering framework preserves similarity in both original and high-frequency spaces, yielding closed-form and iterative GNN propagation mechanisms. The iterative model is computationally efficient and converges to the closed-form model as depth increases.

  • Objective design: The high-pass objective constrains similarity between H and Z in both original and high-frequency filtering spaces.The balance coefficient β controls this constraint through the filtering behavior of {I + βL̃}^1/2.
  • Propagation derivation: The high-pass propagation theorem uses β∈(0, ∞), ζ=1, ξ=1/α−1, and α∈(0, 1].These settings define the propagation process associated with the flexible high-pass convolutional kernel.
  • Iterative approximation: The iterative approximation avoids constructing the dense inverse matrix required by the closed-form solution.It provides a computationally efficient alternative for deep GNN propagation.
  • Convergence: When K→∞, GNN-HF-iter converges to GNN-HF-closed with the same propagation result as Eq. (39).The paper therefore provides closed and iterative forms of the same high-pass propagation strategy.
  • GNN-HF construction: GNN-HF applies propagation to H and L̃H, encoding feature information from both original and high-frequency spaces.The closed-form mechanism uses the matrix {(β+1/α)I + (1−β−1/α)Ẫ}^-1 directly on both components.
  • Iterative architecture: GNN-HF-iter uses layer-wise Ẫ neighborhood aggregation and residual connections on H and L̃H while decoupling transformation from aggregation.Its K-layer output is used directly as the propagation result.

5 SPECTRAL EXPRESSIVE POWER ANALYSIS

The analysis compares the spectral filtering coefficients of established and proposed GNNs. Adjustable factors in GNN-LF/HF increase coefficient flexibility, expressive power, and resistance to over-smoothing, while their limiting distributions retain input-feature and graph-structure information.

  • Analysis setup: The analysis studies polynomial filters of order K and compares their coefficients across different GNN propagation mechanisms.For GNN-LF/HF, the coefficients are examined to assess spectral expressive power under flexible polynomial filtering.
  • GNN-LF analysis: GNN-LF filter coefficients vary with order k and are controlled by adjustable factors α and μ.This dependence improves spectral-filter flexibility and helps alleviate over-smoothing.
  • Comparative analysis: SGC and K-layer graph convolutions use fixed constant filtering coefficients, limiting expressive power and contributing to over-smoothing.PPNP has greater filtering flexibility because its coefficients change with α.
  • Comparative analysis: GNN-LF/HF are more expressive than PPNP and SGC/GCN because adjustable α, μ, or β improve their ability to fit arbitrary polynomial-filter coefficients.The same adjustable factors help these models alleviate over-smoothing.
  • Limit behavior: PPNP, GNN-LF, and GNN-HF converge to distributions carrying information from both input features and graph structure.This property helps reduce over-smoothing even as the number of layers approaches infinity.

6 EXPERIMENTS

Experiments evaluate GNN-LF/HF on benchmark node-classification datasets against traditional, spectral, spatial, and deep GNN baselines. The proposed models consistently achieve leading performance, approximate their closed forms with 10 propagation steps, and maintain performance as depth increases.

  • 6.2 Node Classification: GNN-LF and GNN-HF consistently outperform all state-of-the-art baselines on all evaluated datasets.The best and runner-up results are always achieved by GNN-LF/HF.
  • 6.2 Node Classification: Ten propagation steps effectively approximate the closed-form GNN-LF/HF models in their iterative versions.This comparison uses the fixed propagation depth selected for the iterative models.
  • 6.2 Node Classification: PPNP and APPNP outperform GCN and SGC because their propagation objectives include a feature-fitting term.APPNP also benefits from using original features and decoupling layer-wise nonlinear transformations.
  • 6.3 Propagation Depth Analysis: GNN-LF/HF and APPNP alleviate over-smoothing because accuracy does not drop as propagation depth increases.GCN and SGC instead suffer from over-smoothing, while JKNet and IncepGCN still degrade with increasing depth.
  • 6.4 Model Analysis: GNN-LF/HF use adjustable impact factors α, μ, and β to balance structural and feature information during propagation.α adjusts the regularization weight, while μ and β balance different filters and feature information.
  • 6.4 Model Analysis: GNN-LF performs best for α∈[1e-2, 5e-1] and μ around [0.6, 0.9], while GNN-HF uses the same α range and can degrade with larger β.The models maintain stable performance across a wide range of impact-factor values.

7 CONCLUSION

The paper connects diverse GNN propagation mechanisms through a flexible objective-optimization framework. It proposes low-pass and high-pass GNNs, analyzes their expressive power, and reports superior performance over state-of-the-art models on real-world datasets.

  • 7 CONCLUSION: The unified framework provides a global view for understanding different GNNs and identifying weaknesses in existing propagation mechanisms.It also supports designing novel GNNs through adjustable convolutional kernels.
  • 7 CONCLUSION: The proposed GNNs use adjustable convolutional kernels with low-pass and high-pass filtering capabilities.Their expressive power is analyzed theoretically.
  • 7 CONCLUSION: Extensive experiments demonstrate superior performance of the proposed GNNs over state-of-the-art models on real-world datasets.

A.1 Proof of Theorem 3.2

This proof derives a closed-form propagation solution from the optimization objective and uses matrix decomposition to obtain a first-order graph-convolution approximation.

  • A.1 Proof of Theorem 3.2: The objective has the closed-form solution Ẑ = (I + L̃)^−1H.The solution is then decomposed to derive a first-order truncated form.
  • A.1 Proof of Theorem 3.2: The first-order truncated decomposition provides an approximation of the graph-convolution operation.The framework therefore gives an optimization-based explanation of graph convolution.

A.2 Proof of Theorem 4.4

This proof relates iterative GNN-HF propagation to its closed-form solution by expanding the iteration and establishing convergence under a coefficient condition.

  • A.2 Proof of Theorem 4.4: GNN-HF-iter is defined through an iteration equation and has a corresponding closed-form solution using the same transformed features H = fθ(X).
  • A.2 Proof of Theorem 4.4: After K propagation layers, GNN-HF-iter admits an expansion whose convergence is established under the stated coefficient condition.The converging result is shown to equal the equation used to calculate GNN-HF-closed.

A.3 Expressive Power Analysis

The analysis characterizes SGC polynomial filtering as using fixed coefficients, while analogous expansions are examined for PPNP and GNN-HF.

  • SGC: SGC’s K-layer operations act as an order-K spectral polynomial filter with fixed coefficients, which limits expressive power and leads to over-smoothing.
  • SGC: For SGC, the k-th polynomial filtering term is represented as θ_k L̃^k, with coefficients fixed for each k.
  • PPNP: The PPNP analysis rewrites its propagation using the normalized graph Laplacian and expands it into polynomial filtering terms with corresponding coefficients.
  • GNN-HF: The GNN-HF analysis likewise derives a filtering expression from its propagation result and examines coefficients for powers of the normalized graph Laplacian.
  • Coefficient analysis: The appendix separately identifies coefficient cases for intermediate and highest-order powers of the normalized graph Laplacian.
Loading 2101.11859v1…