PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Representation Learning via Adaptive Expectile Aggregation

Tianyi Zhu, Wei Lan

arXiv:2610.37450v1stat.MLcs.LG

TL;DR

Mean aggregation may miss class-relevant distributional differences in graph neighborhoods, especially in heterophilic settings. This paper introduces ExpectileGCN, which learns an expectile aggregation level and establishes theoretical guarantees. Its risk analysis and benchmark experiments report advantages over mean aggregation and improved robustness under evaluated perturbations.

  • Problem

    Mean aggregation can obscure class-relevant neighborhood distribution differences, including scale or shape differences when class means are similar.

    Source: §1 · p. 2

  • Method

    ExpectileGCN learns an expectile level for neighborhood aggregation and uses sigmoid smoothing with fixed-point iterations for end-to-end optimization.

    Source: §1 · p. 2

  • Results

    Expectile aggregation can lower classification risk than mean aggregation under the studied heterophilic models, while ExpectileGCN performs competitively across graph structures and improves robustness under evaluated perturbations.

    Source: §1 · pp. 2–3, §5 · pp. 19, 21

  • Takeaways & Limitations

    The analysis indicates that aggregation can use class-dependent distributional information even when individual neighbors provide weak signals.

    Source: §1 · p. 2

    The current model uses a common expectile level; adapting it across nodes or local graph structures is proposed as future work.

    Source: §5 · p. 21

Abstract

from arXiv · show

Graph neural networks (GNNs) rely critically on neighborhood aggregation, yet conventional mean aggregation may fail to capture class-relevant distributional information, particularly in heterophilic graphs. We propose ExpectileGCN, an adaptive graph aggregation framework that introduces a learnable expectile level to capture neighborhood information beyond the mean. The proposed operator continuously adjusts aggregation between minimum- and maximum-type behaviors, with mean aggregation as a special case. A differentiable approximation based on sigmoid smoothing and fixed-point iterations enables end-to-end optimization. Theoretically, we establish stability properties and transductive generalization guarantees for ExpectileGCN. We further investigate its classification risk under heterophilic neighborhood models. For informative neighborhoods, we show that expectile aggregation can exploit class-dependent scale differences to achieve a classification advantage over mean aggregation. Under a local asymptotic regime with diminishing per-neighbor label informativeness, we establish that this advantage can persist in terms of limiting classification risk. Experiments on homophilic and heterophilic benchmark graphs demonstrate strong predictive performance and improved robustness under feature corruption and structural perturbations.

1 Introduction

The introduction motivates aggregation that can capture class-relevant neighborhood distributions when mean aggregation obscures differences, and presents ExpectileGCN as a learnable alternative. It relates this approach to statistical and parameterized aggregators, then outlines its theoretical guarantees, risk analysis, and benchmark evaluation.

1 Introduction

  • Heterophilic neighborhoods can retain class-relevant distributional information, but similar class means with different scales or shapes can be poorly separated by mean aggregation.Expectiles can yield distinct centers for distributions with coincident means and different scales.Source: §1 · p. 2
  • Learnable expectile aggregation adapts to neighborhood message distributions, while sigmoid smoothing and fixed-point iterations support end-to-end optimization.The expectile level controls asymmetric weighting; at τ = 1/2, aggregation reduces to the mean.Source: §1 · p. 2

1.2 Contributions

  • The paper establishes stability properties and transductive generalization guarantees for ExpectileGCN under suitable conditions.Its contributions describe bounds on transductive Rademacher complexity and the resulting training–test loss gap.Source: §1 · p. 2, §1.2 · p. 3

1 Introduction

  • Under fixed and diminishing neighborhood signals, expectile aggregation can achieve lower classification risk than mean aggregation by using distributional information.The results cover a fixed heterophilic mixing profile and a local asymptotic regime with weakening per-neighbor class information.Source: §1 · p. 2, §1.2 · pp. 3–4
  • ExpectileGCN shows competitive predictive performance on homophilic and heterophilic benchmarks and improved robustness under evaluated feature and structural perturbations.The introduction reports standard node-classification results alongside tests under feature corruption and structural perturbations.Source: §1 · pp. 2–3

1.1 Related works

  • Prior work uses robust statistics or combines neighborhood summaries, whereas ExpectileGCN parameterizes one aggregation statistic to vary continuously.PNA combines statistics such as mean, maximum, minimum, and standard deviation; GMGCN learns an Lp-based operator.Source: §1.1 · p. 3

2 Estimation and Inference of ExpectileGCN

ExpectileGCN replaces fixed mean aggregation with a learnable, tail-sensitive neighborhood summary and uses a smoothed fixed-point procedure to incorporate it into a two-layer GNN. The section defines the graph notation, aggregation operator, implementation, architecture, and computational costs.

2.1 Notation

  • The graph notation defines each aggregation neighborhood to include the node itself and uses a row-normalized adjacency matrix with self-loops for propagation weights.The normalized weights are nonnegative and sum to one for each node, including isolated nodes.Source: §2.1 · p. 4

2.2 Expectile Aggregation

  • Expectile aggregation emphasizes larger neighbor values when τ > 0.5, smaller values when τ < 0.5, and reduces to the mean at τ = 0.5.The operator summarizes each feature coordinate using an expectile level that adjusts the asymmetric weighting of neighbor deviations.Source: §2.2 · pp. 4–5

2.3 Numerical Approximation of Expectile Aggregation

  • Sigmoid smoothing replaces indicator-based asymmetric weights, and fixed-point iterations produce a differentiable approximation that can be jointly optimized with network parameters.The smoothing coefficient is continuously differentiable; under the stated contraction conditions, the iteration converges to a unique smoothed fixed point.Source: §2.3 · pp. 6–7

2.4 ExpectileGCN

  • The two-layer ExpectileGCN applies expectile aggregation to input features and then to activated hidden representations, using the second-layer outputs as node-classification logits.The architecture uses learnable weight matrices and separate expectile parameters for its two layers.Source: §2.4 · pp. 7–8

2.5 Computational Complexity.

  • For fixed iteration count T, expectile aggregation costs O(T(N + |E|)) per layer; unlike SoftMedoid, it requires no pairwise neighborhood comparisons.The paper gives SoftMedoid's worst-case cost as O(N(dmax + 1)^2).Source: §2.5 · pp. 8–9

3 Theoretical Analysis of ExpectileGCN

The section analyzes ExpectileGCN’s transductive complexity and generalization gap under boundedness and contraction assumptions, and examines when expectile aggregation can reduce classification risk relative to mean aggregation. In particular, it studies class-dependent message scales and conditions under which an expectile advantage persists as per-neighbor label informativeness vanishes.

3.1 Definitions and Assumptions

  • Under bounded features and parameters and a uniform contraction margin, ExpectileGCN has uniformly bounded implicit representations and unique layer-wise fixed points.The contraction condition also controls sensitivity to model parameters; its sufficient condition becomes more stringent as smoothing sharpness increases.Source: §3.1 · pp. 10–11

3.2 Generalization Analysis

  • With fixed architectural and stability constants, transductive Rademacher complexity decreases at O((m + u)^−1/2), and the generalization gap vanishes at that rate when train and test sets remain fixed positive proportions.The bound is uniform over admissible parameters and expectile levels and follows from sampling without replacement on a fixed graph.Source: §3.2 · pp. 11–12

3.3 Neighborhood Informativeness and Aggregation Risk

  • The risk comparisons show that expectile aggregation can use class-dependent message scale information missed by means, including when each neighbor’s label informativeness weakens.The analysis compares aggregation summaries on the same neighborhood messages across K ≥ 3 equally likely classes.Source: §3.3 · pp. 12–13

3.3.1 Fixed Neighborhood Information: A Finite Neighborhood Risk Bound

  • Under heterophilic mixing, separated class scales, and sufficiently large neighborhoods, the expectile nearest-center classifier has lower risk than even the optimal classifier based on the mean aggregate.Theorem 3 also gives an exponentially decaying upper bound on their risk ratio as neighborhood size increases.Source: §3.3.1 · pp. 13–14

3.3.2 Weak Neighborhood Information: A Local Efficiency Comparison

  • Under local alternatives with diminishing neighbor informativeness and additional amplitude information, Theorem 4 establishes a risk advantage for a fixed expectile level τ ≠ 1/2.The local construction balances weakening class differences against increasing neighbor counts, while retaining an independent self-message.Source: §3.3.2 · pp. 14–15
  • Under the additional amplitude condition, a single expectile level achieves smaller limiting classification risk than mean aggregation as individual neighbors’ label informativeness approaches zero.The expectile improves effective class-center separation relative to sampling variability, extracting weak distributional signal more efficiently even when the mean remains predictive.Source: §3.3.2 · p. 15
  • Theorems 3 and 4 establish complementary benefits: a stronger finite-neighborhood risk guarantee for scale-based class information and an advantage that persists as per-neighbor information weakens.Together, the results show that the aggregation statistic affects how neighborhood information is converted into node-classification accuracy.Source: §3.3.2 · p. 15

4 Numerical Experiments

The experiments assess ExpectileGCN on homophilic and heterophilic node-classification benchmarks and under feature and structural perturbations. They report strong aggregate predictive and robustness rankings, alongside training-time comparisons and the settings used to evaluate them.

4 Numerical Experiments

  • Experiments cover both benchmark classification and controlled feature and topology corruption, with five-run mean and standard deviation reporting.Models use a shared 60%/20%/20% train/validation/test split; ExpectileGCN uses a learnable expectile level per layer, initialized at τ = 0.5, with s = 1 and T = 3 fixed-point iterations.Source: §4 · p. 16, §4.2 · p. 17

4.1 Evaluation of the Estimation Model

  • The evaluation compares conventional and spectral GNNs with robust-aggregation methods, using shared dataset splits and hyperparameter tuning protocols.Baselines include GCN, GAT, AGNN, APPNP, JacobiConv, MedianGCN, SoftMedoidGCN, and GMGCN.Source: §4.1 · p. 16

4.3 Evaluation on Node Classification Benchmarks

  • ExpectileGCN ranks first among nine methods, with average ranks of 2.96 across thirteen datasets and 2.85 across eight heterophilic datasets.It achieves the best results on pubmed and film and remains competitive on the other named benchmarks.Source: Table 2 · p. 17, §4.3 · p. 17
  • ExpectileGCN is faster than MedianGCN and SoftMedoidGCN on most datasets, while GMGCN is generally faster on smaller graphs.The training-time heatmap reports wall-clock costs averaged over five runs; ExpectileGCN is faster than GMGCN on pubmed, amazon-ratings, and roman-empire.Source: §4.3 · pp. 17–18, Figure 2 · p. 18

4.4 Robustness under Feature and Structural Perturbations

  • Feature noise is Gaussian with σ ∈ {0.5, 1.0}; structural perturbations remove same-label edges or add different-label edges at levels p ∈ {0, 0.2, 0.4, 0.6}.The perturbation experiments cover most benchmark datasets, excluding two with relatively low benchmark performance; perturbation settings are repeated with five random seeds.Source: §4.4 · pp. 18–19
  • Across perturbation settings, ExpectileGCN has the best All-rank (1.88) and Heter-rank (1.96), versus JacobiConv’s 2.53 and 2.72, respectively.It ranks first on six of thirteen datasets.Source: Table 3 · p. 19, §4.4 · p. 19
  • As perturbation levels rise, ExpectileGCN generally remains competitive, particularly on the heterophilic chameleon dataset.The authors describe the theorems as complementary explanation for potential benefits, not as direct characterizations of robustness under graph perturbations.Source: §4.4 · p. 19

5 Conclusion

ExpectileGCN uses a learnable expectile level to capture neighborhood information beyond the mean, and the paper establishes stability and transductive generalization guarantees. Theoretical analysis and experiments report lower classification risk under specified heterophilic conditions and competitive performance with improved robustness; the conclusion identifies directions for extending the model.

5 Conclusion

  • ExpectileGCN introduces learnable expectile aggregation to capture neighborhood information beyond the mean, with stability properties and transductive generalization guarantees.The expectile level adapts the weighting of neighborhood messages.Source: §5 · p. 19
  • Expectile aggregation can achieve lower classification risk than mean aggregation by using informative neighborhood distributional structure, with an advantage that can persist as individual-neighbor information weakens.The conclusion also reports competitive predictive performance and improved robustness under feature and structural perturbations.Source: §5 · p. 21
  • The current model uses a common expectile level; adapting it across nodes or local graph structures is proposed for heterogeneous neighborhood distributions.The authors also propose extensions to dynamic graphs, hypergraphs, and other higher-order structures.Source: §5 · p. 21

Appendix

The appendix points readers to supplementary proofs and auxiliary lemmas and reports additional robustness and hyperparameter-sensitivity results.

Appendix

  • The appendix provides additional robustness and hyperparameter-sensitivity results, while proofs and auxiliary lemmas appear in the Supplementary Material.Section and lemma numbers prefixed by S refer to that material.Source: Appendix · p. 22

A1.1 Additional Robustness Visualizations

Appendix A1.1 presents additional robustness visualizations for one homophilic and three heterophilic datasets, using the main-text perturbation protocol.

A1.1 Additional Robustness Visualizations

A1.2 Hyperparameter Sensitivity Analysis

ExpectileGCN performs stably across varied fixed-point iteration counts and sigmoid sharpness settings, with limited iterative refinement and moderate smoothing performing comparably to larger or sharper settings.

A1.2 Hyperparameter Sensitivity Analysis

  • The analysis covers nine homophilic and heterophilic benchmark datasets, reporting mean accuracy and standard deviation over five runs for each configuration.Table A1 varies fixed-point iterations T and smoothing sharpness s.Source: A1.2 Hyperparameter Sensitivity Analysis · p. 24, Table A1 · p. 24
  • ExpectileGCN maintains stable performance across a wide range of iteration counts and smoothing sharpness settings.The sensitivity analysis reports small variations in mean accuracy and standard deviation.Source: A1.2 Hyperparameter Sensitivity Analysis · pp. 24–25, Table A1 · p. 24
  • The results show performance comparable to larger iteration budgets, indicating that implicit expectile representations require only limited iterative refinement across the evaluated iterative-depth settings.The analysis considers T ∈{1, 2, 4, 8} across nine benchmark datasets, reporting mean classification accuracy and standard deviation over five independent runs.Source: A1.2 Hyperparameter Sensitivity Analysis · pp. 24–25
  • Smoothing sharpness s = 3 or 5 performs comparably to sharper approximations such as s = 10.This indicates that performance is not sensitive to the precise smoothness specification.Source: A1.2 Hyperparameter Sensitivity Analysis · pp. 24–25
Loading 2610.37450v1…