PaperlayerView exact revision on arXiv

Source-linked AI summary

Permutation Equivariant Graph Framelets for Heterophilous Graph Learning

Jianfei Li, Ruigang Zheng, Han Feng, Ming Li, Xiaosheng Zhuang

arXiv:2306.04265v3cs.LGcs.AIcs.SImath.FA

TL;DR

Heterophilous graphs motivate learning methods that reach beyond 1-hop neighborhoods, while existing graph framelets may depend on node ordering. The paper constructs permutation-equivariant Haar-type graph framelets and builds PEGFAN around them. Results report improved node classification from combining framelets with multi-hop aggregation on synthetic and real-world data.

  • Problem

    Graph framelet systems may change with node ordering, leaving permutation equivariance a concern for robust graph learning.

    Source: §I · p. 1

  • Method

    The paper constructs permutation-equivariant Haar-type graph framelets and integrates them into PEGFAN for multi-scale graph learning.

    Source: §I · p. 2

  • Results

    Combining graph framelets with multi-hop aggregation increases node-classification performance on synthetic and real-world heterophilous data.

    Source: §VI · p. 10

  • Takeaways & Limitations

    The proposed framelets serve as an alternative and supplement to multi-hop aggregation using powers of adjacency matrices.

    Source: §VI · p. 10

    Texas, Wisconsin, and Cornell test sets contain at most 51 nodes, making those experiments relatively and statistically insignificant.

    Source: D. Comments on Benchmark Dataset… · p. 10

Abstract

from arXiv · show

The nature of heterophilous graphs is significantly different from that of homophilous graphs, which causes difficulties in early graph neural network models and suggests aggregations beyond the 1-hop neighborhood. In this paper, we develop a new way to implement multi-scale extraction via constructing Haar-type graph framelets with desired properties of permutation equivariance, efficiency, and sparsity, for deep learning tasks on graphs. We further design a graph framelet neural network model PEGFAN (Permutation Equivariant Graph Framelet Augmented Network) based on our constructed graph framelets. The experiments are conducted on a synthetic dataset and 9 benchmark datasets to compare performance with other state-of-the-art models. The result shows that our model can achieve the best performance on certain datasets of heterophilous graphs (including the majority of heterophilous datasets with relatively larger sizes and denser connections) and competitive performance on the remaining.

I. INTRODUCTION

Heterophilous graphs challenge 1-hop, homophily-based GNNs, motivating multi-scale information beyond neighborhood aggregation. The paper constructs permutation-equivariant Haar-type graph framelets and uses them in PEGFAN.

I. INTRODUCTION

  • Heterophilous graphs differ spatially and spectrally from homophilous graphs, while multi-hop adjacency aggregation can over-smooth features and create dense computation and storage burdens.The paper therefore explores graph framelets as an alternative spatial resolution for multi-scale extraction.Source: §I · p. 1
  • Graph framelets can change under node reordering, potentially making network outputs unstable; this paper constructs Haar-type framelets with permutation equivariance.PEGFAN inherits this property from the proposed framelets.Source: §I · pp. 1–2

III. PERMUTATION EQUIVARIANT GRAPH FRAMELETS

  • The proposed Haar-type framelets use hierarchical graph structure for scales and provide permutation equivariance, sparse representation, and efficient computation.The framelets are integrated with adjacency matrices as multi-channel inputs for PEGFAN, which uses attention and concatenation for multi-scale extraction.Source: §I · p. 2

II. RELATED WORK

  • In heterophilous settings, theoretically supports aggregation beyond the 1-hop neighborhood and ego- and neighbor-embedding separation; cited graph wavelet/framelet work includes spectral-type, and Haar-type systems.Source: §II · p. 2

A. Preliminaries

  • A hierarchical clustering partitions graph nodes into nested sets, with each level refining the preceding one; the construction uses these levels to define graph scales.The paper frames graph signals as elements of a Hilbert space and describes tight frames as collections that reconstruct each signal from its inner-product coefficients.Source: A. Preliminaries · p. 3

B. Main Construction

The construction defines graph framelets from a hierarchical partition and child-cluster weights. A binary Haar choice yields a tight frame with permutation-equivariant properties.

B. Main Construction

  • The general construction defines unit scaling vectors from the finest clusters upward and derives framelet vectors from child-cluster weights and matrices BΛ.The resulting scales correspond to levels of the hierarchy, offering a multi-scale representation distinct from k-hop neighborhoods.Source: B. Main Construction · pp. 3–4
  • A graph framelet system is tight when its matrices and weights satisfy the stated conditions BΛB⊤BΛ = BΛ, BΛpΛ = 0, and Rank(BΛ) = LΛ − 1.These conditions characterize tightness for the framelet system formed from scaling vectors and framelet vectors.Source: B. Main Construction · p. 4
  • The binary Haar construction uses equal child-cluster weights and permuted pairwise difference vectors with unnormalized nonzero entries in {1, −1}.The construction is a particular matrix splitting of I − pΛpΛ⊤; more general vectors can also be permuted to form BΛ.Source: B. Main Construction · p. 4
  • The binary Haar system is a tight frame for L2(G) for any permitted starting level j0.The hierarchical partition PK is not prescribed and may be generated from edges alone or from edges and node features.Source: B. Main Construction · p. 4

C. Sparsity

The binary Haar construction yields sparse framelet vectors and preserves sparsity of transformed signals under a bounded cluster-size condition.

C. Sparsity

  • Each binary Haar framelet vector has at most two nonzero values per child-level construction, and high-level framelets are well-localized and sparse when the hierarchy is balanced.The maximum number of children at level j is denoted Lj in the stated sparsity bound.Source: C. Sparsity · p. 4
  • Sparse framelet coefficients are relevant to feature extraction, and piecewise-constant signals such as one-hot label encodings motivate analyzing that property for node classification.The transform maps a signal f to coefficients through inner products with the framelet system.Source: C. Sparsity · p. 5
  • For binary Haar framelets with maximum cluster branching at most h, the transform satisfies ∥f̂∥0 ≤ (K − 1)(h − 1)∥f∥0.When each cluster has h children, the coefficient count is O(h log_h n) times the signal sparsity, while the framelet system has O(nh) elements.Source: C. Sparsity · p. 5

D. Efficiency

The paper bounds the size and computation of its binary Haar framelet matrix under a bounded branching assumption. It also proves equivariance under node and partition reorderings.

D. Efficiency

  • The paper contrasts sparse computation for binary Haar framelets with graph Fourier basis generation, whose computational and space complexities can reach O(n^3) and O(n^2).These bounds are cited as reasons graph Fourier basis generation can be inflexible for large graphs with nonsparse Laplacians.Source: D. Efficiency · p. 5
  • With maximum branching h and n = O(h^(K−1)), the framelet matrix has O(nh) vectors, while generation and nonzero storage each require O(nh log_h n).The coefficient vector can be computed in O(nh); the authors note that h is usually small in practice.Source: D. Efficiency · p. 5

E. Permutation Equivariance

  • The binary Haar framelet construction is equivariant to node permutations, partition permutations, and their combination.For partition permutations, framelets correspond up to a permutation of the framelet vectors and signs of ±1.Source: E. Permutation Equivariance · p. 6
  • Theorem 4's framelet equivariance implies that PEGFAN is permutation equivariant; the paper focuses on output consistency for node classification.The authors note that permutation equivariance is less straightforward for graph wavelets and framelets than for common GNN operations.Source: E. Permutation Equivariance · p. 6

IV. GFNN MODEL

PEGFAN integrates binary Haar graph framelets with adjacency-based inputs in a graph framelet neural network. Its channel design combines multi-scale framelet projections with powers of the adjacency matrix, and its output is permutation equivariant under the stated permutation of graph data and framelets.

IV. GFNN MODEL

  • PEGFAN is introduced as a graph framelet neural network integrating the constructed binary Haar graph framelets.The architecture takes feature matrix X as input, with operations determined by adjacency matrix A and framelet system {F0, ..., FK−1}.Source: §IV · p. 6, Figure 3 · p. 7
  • The model uses a two-layer network with multiple input channels, trainable channel attention weights, row normalization, and trainable linear parameters.It minimizes cross-entropy on the labeled nodes.Source: §IV · p. 6
  • Under a node permutation, PEGFAN's output changes by the same permutation when its features, adjacency matrix, and framelet system are permuted accordingly.This is the condition stated in Proposition 2.Source: §IV · p. 6
  • PEGFAN combines framelet projections and adjacency-matrix powers as input channels, exploiting both multi-scale and short- and long-range graph information.For heterophilous graphs, the listed channels include X, A^kX, and framelet projections of X or AX.Source: §IV · pp. 6–7

V. EXPERIMENTS

The experiments compare PEGFAN with other models on a synthetic dataset and nine benchmark datasets. Synthetic results show gains for framelet channels in some settings, while the benchmark section describes the dataset and evaluation setup but the supplied passages do not report its comparative accuracy outcomes.

A. Experiment on Synthetic Dataset

  • The synthetic experiment uses four-class heterophilous graphs with 3,000 nodes, fixed Gaussian features, and 48%/32%/20% train/validation/test splits.The hyperparameter γ controls the tendency to sample edges from a uniform neighborhood-class distribution; larger γ makes class distributions less distinguishable.Source: A. Experiment on Synthetic Dataset · p. 7

B. Comments on the Synthetic Dataset Experiment

  • In some synthetic settings, Type b framelet channels improve over FSGNN by more than 10%, while performance generally declines as neighborhood class distributions become more uniform.With closer class-feature means, Type b gains are smaller than in Table I; Type c performs similarly to FSGNN in both tables.Source: B. Comments on the Synthetic Dataset… · pp. 7–8, Table I · p. 7, Table II · p. 8
  • Type a framelet-only inputs are sensitive to h, and the authors report that simple unsupervised clustering loses connectivity information, motivating 1–3-hop aggregation alongside coarse-scale projections.Type a results vary less across γ and are better when γ is close to 1.Source: B. Comments on the Synthetic Dataset… · p. 8

C. Experiments on Benchmark Datasets

  • The benchmark evaluation covers nine datasets, including three homophilous citation networks and six heterophilous datasets, using public data splits.Table III is identified as reporting dataset statistics, classification accuracy, and standard deviation, but the supplied passages do not provide its cell values or comparative outcomes.Source: C. Experiments on Benchmark Datasets · p. 8, Table III · p. 9
  • The benchmark implementation adopts FSGNN code and settings for PEGFAN integration, while FSGNN is separately grid-searched after reproduction results differed slightly from those reported in.The authors set PEGFAN's input-channel parameter r to 3 and cite results for several other models from.Source: C. Experiments on Benchmark Datasets · p. 8

D. Comments on Benchmark Dataset Experiments

Across the nine benchmarks, PEGFAN with h = 8 and Type c ranks first on average, while the strongest-performing methods vary by graph type and dataset. PEGFAN performs best on Chameleon and Squirrel, but the paper cautions against firm comparisons on the small datasets and Actor.

D. Comments on Benchmark Dataset Experiments

  • GEOM-GCN, GCNII, and GPRGNN give the best performances on the three homophilous datasets, while FSGNN and PEGFAN are the best-performing models on heterophilous datasets.The paper reports similar performance to other methods on the homophilous datasets, where it says further multi-scale information is not needed.Source: D. Comments on Benchmark Dataset… · pp. 9–10
  • At most 51 test nodes in Texas, Wisconsin, and Cornell make their results statistically limited; the paper says it is not reasonable to declare one method better than another.A correctly predicted node accounts for at least 1.9% of accuracy; PEGFAN is best on Cornell and second on Texas, while FSGNN is best on Wisconsin and Texas.Source: D. Comments on Benchmark Dataset… · p. 10
  • About 35% accuracy across models on Actor leads the authors to call comparisons among methods unreasonable; WRGAT has the best performance.Source: D. Comments on Benchmark Dataset… · p. 10
  • PEGFAN performs best on Chameleon and Squirrel, which the paper describes as large, dense graphs with distinguishable neighborhood-class distributions.The paper links density to forming better hierarchical partitions and graph framelets, and cites for the distinguishability of these datasets' neighborhood distributions.Source: D. Comments on Benchmark Dataset… · p. 10
  • PEGFAN with h = 8 and Type c ranks first among the compared methods by average performance across the nine benchmarks.The paper reports that its Type c methods generally have high average overall performance.Source: D. Comments on Benchmark Dataset… · p. 10

VI. CONCLUSION

  • The conclusion reports that combining graph framelets with multi-hop aggregation increases node-classification performance on heterophilous synthetic and real-world data, and identifies more sophisticated hierarchical partitioning as future work.In the synthetic case, the model shows significant increases against deterioration in neighborhood distribution; the paper says the results are consistent with benchmark patterns.Source: §VI · p. 10

A. Proofs of theoretical results

The proofs establish tight-frame decompositions across hierarchical scales, sparse framelet representations, and equivariance under node and partition permutations. They also bound the framelet system’s size and construction cost, and show that PEGFAN’s predictions permute with its input.

A. Proofs of theoretical results

  • The conditions on BΛ and pΛ yield V_{j+1}=V_j ⊕ W_j and tight-frame decompositions across scales.The proof iterates these conditions from j0 to K, where VK=L2(G).Source: A. Proofs of theoretical results · p. 10
  • For f, the framelet coefficients satisfy ∥F⊤f∥0 ≤ (h−1)(K−1)∥f∥0.Each nonzero input node contributes at most (h−1)(K−1) nonzero coefficients.Source: A. Proofs of theoretical results · p. 11
  • The binary graph Haar framelet system contains O(nh) elements, and computing its nonzero entries requires O(nh log_h n) multiplication and addition evaluations.These bounds are stated for the hierarchical construction.Source: A. Proofs of theoretical results · p. 11
  • The number of nonzero entries in F is bounded by O(nh log_h n).The construction bounds the entries per scaling vector and framelet, then sums across levels.Source: A. Proofs of theoretical results · p. 11
  • Node permutations reorder the scaling and framelet vectors, while partition permutations preserve scaling vectors up to index permutation and reorder framelets up to signs.The partition-permuted framelet matrices are related by a permutation matrix and a diagonal sign matrix.Source: A. Proofs of theoretical results · pp. 11–12
  • PEGFAN’s predictions satisfy ŶP=PŶ under node permutation because its row normalization and softmax are row-wise and its activation is elementwise.The proof applies these operations to channels that differ by the input permutation.Source: A. Proofs of theoretical results · p. 12

B. Fast Decomposition and Reconstruction Algorithms

The algorithms compute framelet coefficients and reconstruct graph signals iteratively, without forming the full framelet system. Both have computational complexity O(nh).

B. Fast Decomposition and Reconstruction Algorithms

  • Decomposition iteratively computes the coefficient vector from a graph signal using the framelet transform matrices CΛ.For each cluster Λ, the transform maps its lowpass coefficients to xΛ and highpass coefficients y(Λ,m).Source: B. Fast Decomposition and… · pp. 12–13
  • Reconstruction iteratively recovers the graph signal from its framelet coefficients across the spaces Vj0 ⊕ Wj0 ⊕ · · · ⊕ WK−1.The reconstruction algorithm computes rΛ at each level.Source: B. Fast Decomposition and… · p. 13
  • The algorithms avoid forming the full framelet system, requiring only pΛ, BΛ, and CΛ.The paper identifies this as implying efficiency in applications using the framelet system.Source: B. Fast Decomposition and… · p. 13
  • Both decomposition and reconstruction have computational complexity O(nh).Theorem 5 states this bound for the algorithms described in Equations (17) and (18).Source: B. Fast Decomposition and… · p. 13

C. Experiment Details on the Synthetic Dataset

The synthetic experiments vary cross-class neighborhood similarity (CCNS) through a mixing parameter γ. The reported CCNS patterns change as uniform sampling has greater influence.

C. Experiment Details on the Synthetic Dataset

Algorithm 4 [52]

Algorithm 4 generates graph edges by mixing uniform and label-conditioned sampling. It adds an edge only if that edge is not already present.

Algorithm 4 [52]

  • The algorithm takes nodes, an edge count N, class distributions {Dc}, labels C, and mixing parameter γ as inputs.It initializes an empty edge set and a counter before sampling.Source: Algorithm 4 [52] · p. 14
  • For each sampled node i, it chooses a class uniformly from C with probability γ, or from Dyi otherwise, then samples node j uniformly from that class.This mixes label-independent and label-conditioned neighbor selection.Source: Algorithm 4 [52] · p. 14
  • The algorithm adds (i, j) only when the edge is absent, increments the edge counter, and outputs G = (V, E).The loop continues while k ≤ N.Source: Algorithm 4 [52] · p. 14
Loading 2306.04265v3…