PaperlayerView exact revision on arXiv

Source-linked AI summary

Finding Global Homophily in Graph Neural Networks When Meeting Heterophily

Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, Weining Qian

arXiv:2205.07308v1cs.LGcs.AI

TL;DR

Heterophilous graphs challenge local neighbor aggregation because useful homophilous nodes may be distant or excluded by fixed multi-hop neighborhoods. GloGNN and GloGNN++ learn global node correlations for aggregation, accelerate computation to linear time, and achieve favorable performance across broad benchmarks.

  • Problem

    Heterophilous graphs make local smoothing problematic, while multi-hop approaches require difficult personalized neighborhood sizes and omit excluded homophilous nodes.

  • Method

    GloGNN and GloGNN++ learn a coefficient matrix from an optimization problem for global-node aggregation, support signed values, and accelerate aggregation through matrix reordering.

  • Results

    GloGNN++ achieves the first average rank and GloGNN the runner-up across 15 datasets, while the methods perform favorably against 11 competitors.

  • Takeaways & Limitations

    The models provide efficient global aggregation with a theoretically established grouping effect for nodes sharing similar features and local structures.

  • Takeaways & Limitations

    The grouping-effect analysis assumes pairs of nodes approach identical features and local-structure conditions.

Abstract

from arXiv · show

We investigate graph neural networks on graphs with heterophily. Some existing methods amplify a node's neighborhood with multi-hop neighbors to include more nodes with homophily. However, it is a significant challenge to set personalized neighborhood sizes for different nodes. Further, for other homophilous nodes excluded in the neighborhood, they are ignored for information aggregation. To address these problems, we propose two models GloGNN and GloGNN++, which generate a node's embedding by aggregating information from global nodes in the graph. In each layer, both models learn a coefficient matrix to capture the correlations between nodes, based on which neighborhood aggregation is performed. The coefficient matrix allows signed values and is derived from an optimization problem that has a closed-form solution. We further accelerate neighborhood aggregation and derive a linear time complexity. We theoretically explain the models' effectiveness by proving that both the coefficient matrix and the generated node embedding matrix have the desired grouping effect. We conduct extensive experiments to compare our models against 11 other competitors on 15 benchmark datasets in a wide range of domains, scales and graph heterophilies. Experimental results show that our methods achieve superior performance and are also very efficient.

1. Introduction

Traditional GNNs rely on local smoothing, which can fail on heterophilous graphs. GloGNN and GloGNN++ instead use globally learned node correlations to aggregate informative nodes efficiently.

  • Heterophily can make neighbor smoothing produce similar representations for nodes with different labels, harming GNN performance.
  • Multi-hop methods seek homophilous nodes beyond local neighborhoods, but personalized neighborhood sizes are difficult and excluded nodes are ignored.
  • GloGNN characterizes each node using all graph nodes through a coefficient matrix Z(l), whose entries encode node-to-node importance.
  • Matrix multiplication reordering avoids explicit coefficient computation and reduces neighborhood aggregation complexity to linear time.
  • Both Z(l) and the generated embeddings H(l) have a grouping effect, bringing nodes with similar features and local structures closer despite distance.
  • The models combine low-pass and high-pass filters because their learned coefficients can take signed values.
  • GloGNN and GloGNN++ outperform 11 competing methods across 15 benchmark datasets spanning diverse domains, scales and heterophilies.

2. Related Work

Related work extends GNNs to heterophilous graphs through signed filtering, enlarged neighborhoods and multi-relational graph constructions.

  • GNN research includes spectral and spatial models, with methods such as GraphSAGE and GAT aggregating information from nearby neighbors.
  • Heterophily-oriented methods use low-pass and high-pass filters, signed propagation weights, or adaptive fusion of filter outputs.
  • H2GCN enlarges neighborhoods and separates ego from neighbor embeddings, while WRGAT constructs a multi-relational graph with raw and newly added edges.

3. Preliminaries

The preliminaries define graph notation, label-based homophily, and the standard GCN propagation pipeline used as background for the proposed models.

  • The graph is represented as G=(V,E), with adjacency matrix A encoding edge weights and neighborhood N_i containing directly connected nodes.
  • H(l) stores node representations at layer l, X denotes initial node features, and Y contains one-hot ground-truth labels.
  • In this paper, homophily and heterophily concern node labels; edge homophily is the fraction of edges connecting nodes with the same label.
  • GNN convolution consists of feature propagation and aggregation followed by embedding updating.
  • Vanilla GCN uses the normalized affinity matrix  as a low-pass filter and the Laplacian L=I_n− as a high-pass filter.
  • A GCN layer computes H(l+1)=σ(ÂH(l)W(l)), and final representations feed a softmax classifier trained with cross-entropy.

4. Algorithm

GloGNN characterizes each node using global nodes, deriving a signed coefficient matrix through optimization and using it for aggregation. The method accelerates this computation to linear time, while its grouping effect explains similar representations for nodes with similar features and local structures.

  • Coefficient matrix: GloGNN derives a coefficient matrix Z^(l) that measures how strongly each global node characterizes another node.The matrix serves as the weight matrix for global-node information aggregation and allows signed values.
  • Coefficient matrix: GloGNN uses skip connections and an initial embedding that captures both node features and graph connectivity.The parameter γ balances the propagated representation with the initial embedding.
  • Coefficient matrix: The coefficient matrix is optimized using node embeddings, Frobenius regularization, and multi-hop graph reachability regularization.The objective balances representation fidelity with regularization from multi-hop adjacency matrices through β1, β2, and learnable λ_k weights.
  • Aggregation acceleration: Matrix multiplication reordering avoids explicitly computing Z^(l)* and reduces aggregation updates from quadratic dependence on nodes to O(k2n).The implementation computes label-dimensional matrices first; the total update complexity is O(k2n), with k2 ≪ n.
  • Grouping effect: The coefficient matrices and generated embeddings have grouping effect: nodes with similar features and local structures receive similar coefficients and representations, regardless of graph distance.In heterophilous graphs, adjacent dissimilar nodes can consequently receive different embeddings, while structural similarity can reinforce characterization even with lower feature similarity.
  • GloGNN++: GloGNN++ adds horizontal attention through a diagonal matrix Σ that assigns importance to hidden-feature dimensions alongside node-to-node attention.The extended model retains accelerated aggregation and the grouping-effect result.

5. Experiments

GloGNN and GloGNN++ are evaluated against 11 baselines on 15 diverse benchmark datasets, with experiments covering classification performance, efficiency, grouping effects, and global homophily. The models achieve the strongest overall ranking, converge quickly, exhibit grouping effects, and identify distant same-class nodes.

  • Experimental setup: Experiments compare GloGNN and GloGNN++ with 11 baselines on 15 datasets spanning diverse domains, scales, and graph heterophilies.The benchmarks include nine small-scale and six large-scale datasets, using the original papers’ training, validation, and test splits.
  • Performance results: 0.8039 is Wisconsin’s accuracy for GCNII, exceeding MixHop’s 0.7588 and illustrating the advantage of stronger plain-GNN baselines over GCN and GAT.MixHop expands neighborhoods with multi-hop neighbors, while GCNII combines intermediate representations through initial residual and identity mappings.
  • Performance results: H2GCN, WRGAT, and GGCN fail with out-of-memory errors on very large-scale datasets, while ACM-GCN and LINKX do not consistently perform well.For example, ACM-GCN wins on Texas but scores 0.6381 on pokec versus the best result of 0.8305.
  • Performance results: GloGNN++ achieves the first average rank across all datasets, while GloGNN is the runner-up.The authors attribute the performance to using more homophilous neighbors, with GloGNN++ additionally learning the importance of hidden node features.
  • Efficiency study: GloGNN and GloGNN++ converge quickly to the best or runner-up validation results; GloGNN++ is almost 8× faster than ACM-GCN on genius and 2× faster than H2GCN on Penn94.GPR-GNN runs faster but generally performs poorly, whereas H2GCN and ACM-GCN are slower.
  • Grouping effect and global homophily: The coefficient matrix exhibits block-diagonal grouping by ground-truth labels, and GloGNN assigns positive values to distant same-class nodes beyond six hops.Figure 4 visualizes signed coefficient and embedding grouping on Texas, Wisconsin, and Cornell; Figure 5 studies global homophily on six highly heterophilous graphs.

6. Conclusions

GloGNN and GloGNN++ extend GNNs to heterophilous graphs by aggregating global information through learned node relationships, with theoretical and empirical support for effectiveness and efficiency.

  • GloGNN and GloGNN++ generate node embeddings by aggregating information from global graph nodes.
  • Each layer derives a coefficient matrix from an optimization problem, then performs neighborhood aggregation based on the learned relationships.The coefficient matrix describes relationships between nodes.
  • Matrix multiplication reordering accelerates aggregation without explicitly calculating the coefficient matrix.
  • Theoretical proofs show that both the coefficient matrix and generated embedding matrix have the desired grouping effect.This grouping effect is presented as an explanation of model effectiveness.
  • Across 15 datasets, the methods perform favorably against 11 competitors, while remaining efficient and converging very fast.

A. Pseudocodes

The pseudocode takes graph, feature, label, and split information as input, initializes embeddings, iteratively updates them across layers, and returns predictions for unlabeled nodes.

  • The node-classification task learns a mapping from graph nodes to labels to predict labels for unlabeled nodes.
  • GloGNN receives graph structure, node features, labeled-node information, class information, and labeled-node labels as inputs.
  • The algorithm initializes H(0) from X and A, then computes the initial embedding before entering the convolutional loop.
  • The procedure returns the label matrix YU for unlabeled nodes.
  • Each layer calculates Q(l+1) and H(l+1), after which the final embeddings are normalized with Softmax and optimized using cross-entropy.

B. Datasets

The evaluation uses nine small-scale and six large-scale datasets spanning citation, web, actor, Wikipedia, and social-network domains, with varied node features and classification labels.

  • The small-scale evaluation contains nine datasets grouped into four categories.
  • Citation network: Cora, Citeseer, and Pubmed are citation graphs with bag-of-words features and research-field labels, and are homophilous.
  • WebKB: Texas, Wisconsin, and Cornell represent web pages linked by hyperlinks and classify pages into five university-related categories.
  • Actor co-occurrence network: Actor is an actor co-occurrence network using Wikipedia-keyword features to classify actors into five categories.
  • Wikipedia network: Squirrel and Chameleon are Wikipedia web-page subgraphs whose nodes are classified into five categories based on average monthly traffic.
  • The large-scale evaluation adds six datasets released by Lim et al. (2021).
  • Social network: Penn94 and Pokec are social networks using student or user attributes as features and gender or user labels for classification.
  • Citation network: arXiv-year and snap-patents are citation networks whose labels are based on paper posting year or patent grant time.

C. Aggregation acceleration

Aggregation updates are accelerated by applying the Woodbury formula and transforming the original update equation into an equivalent form.

  • The Woodbury formula is used to accelerate updates of H(l+1) in Equation 6.
  • The resulting inverse expression rewrites an n-dimensional matrix operation using an identity term and products involving H(l).
  • Equations 6 and 11 are combined to transform Equation 6 into Equation 7.

D. Proof

The proof establishes grouping effects for the coefficient matrices and node embeddings, using node reachability, optimality conditions, and induction across layers.

  • Proof: The proof characterizes each row of Z(l)* as a coefficient vector representing a node, while each row of Â_k represents k-hop reachability.These representations support the subsequent grouping-effect arguments.
  • Proof: The optimal solution Z(l)* satisfies the stated conditions derived from the optimization objective and its first-order derivative.The proof uses Lemma D.1 and the optimality of Z(l)* in Equation 5.
  • Proof: If two nodes have similar features and local structures, H(0) and Z(0)* exhibit grouping effects as their relevant differences approach zero.The proof derives this from node-feature differences, reachability-related quantities, and equations governing Z(0)*.
  • Proof: The grouping effect propagates through subsequent layers because Z(0)*H(0) has grouping effect and H(l+1) is updated from Z(l)*H(l).Induction then establishes grouping effects for Z(l)*, (Z(l)*)^T, and H(l+1).

E. Ablation study

The ablation study removes feature information, adjacency information, or local regularization to assess their roles in GloGNN across benchmark datasets.

  • E. Ablation study: GloGNN constructs H(0) from low-dimensional embeddings of both the feature and adjacency matrices.The variants GloGNN-na and GloGNN-nf remove adjacency and feature information, respectively, through α=0 or α=1.
  • E. Ablation study: GloGNN-nl removes the multi-hop adjacency regularization term to test the importance of local graph structures.The regularization is part of the coefficient-matrix formulation in Equation 5.
  • E. Ablation study: GloGNN significantly outperforms GloGNN-na and GloGNN-nf on some datasets, although the variants are comparable on others.This supports adaptively learning the relative importance of feature and adjacency information across datasets.
  • E. Ablation study: Figure 6 presents the ablation study comparing GloGNN with its component-removal variants.The supplied caption identifies the figure as an ablation study but does not specify its axes or visual encodings.

F. Experimental setup

Experiments use different hardware and optimizers for small- and large-scale datasets, with hyperparameters selected by validation-set grid search.

  • F. Experimental setup: Nine small-scale datasets are run on CPUs using Adam, while six large-scale datasets use a single Tesla V100 GPU with 32G memory and AdamW.The setup follows the cited optimization procedures for the respective dataset scales.
  • F. Experimental setup: Hyperparameters are tuned through grid search based on validation-set results.The search spaces are listed in Tables 3 and 4 for small- and large-scale datasets.
Loading 2205.07308v1…