Source-linked AI summary
Directional Graph Networks
Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, Pietro Liò
TL;DR
GNNs lack globally consistent anisotropic kernels, limiting directional message passing and expressiveness. The paper uses Laplacian-eigenvector vector fields to project messages into directional derivatives and smoothing, generalizing grid CNNs and improving results across benchmarks. It also reports stronger 1-WL discrimination and mechanisms that counteract over-smoothing, while extreme directional augmentation can reduce performance.
Problem
GNNs generally lack globally consistent anisotropic kernels and specific graph directions, limiting directional message passing and expressiveness.
Method
The method defines graph vector fields from low-frequency Laplacian eigenvectors and projects incoming messages onto them for directional smoothing and derivatives.
Results
The method generalizes CNN convolutions on n-dimensional grids, is more discriminative under the Weisfeiler-Lehman 1-WL test, and achieves state-of-the-art results across evaluated benchmarks.
Takeaways & Limitations
Directional graph networks provide unsupervised graph directions and support efficient message passing across distant communities, counteracting over-smoothing.
Takeaways & Limitations
Excessive rotation or distortion can decrease performance, while larger models are expected to perform better at high angles.
Abstract
from arXiv · showhide
The lack of anisotropic kernels in graph neural networks (GNNs) strongly limits their expressiveness, contributing to well-known issues such as over-smoothing. To overcome this limitation, we propose the first globally consistent anisotropic kernels for GNNs, allowing for graph convolutions that are defined according to topologicaly-derived directional flows. First, by defining a vector field in the graph, we develop a method of applying directional derivatives and smoothing by projecting node-specific messages into the field. Then, we propose the use of the Laplacian eigenvectors as such vector field. We show that the method generalizes CNNs on an $n$-dimensional grid and is provably more discriminative than standard GNNs regarding the Weisfeiler-Lehman 1-WL test. We evaluate our method on different standard benchmarks and see a relative error reduction of 8% on the CIFAR10 graph dataset and 11% to 32% on the molecular ZINC dataset, and a relative increase in precision of 1.6% on the MolPCBA dataset. An important outcome of this work is that it enables graph networks to embed directions in an unsupervised way, thus allowing a better representation of the anisotropic features in different physical or biological problems.
1 Introduction
The paper introduces globally consistent directional flows for graph message passing, addressing the absence of full-graph anisotropic kernels in GNNs. Using Laplacian eigenvectors, the method guides aggregation directionally and improves theoretical expressiveness and benchmark performance.
- Existing GNN methods largely use symmetric kernels, while available asymmetric mechanisms depend on local structures or features rather than full graph directional flows.
- The proposed framework projects neighboring messages onto globally defined vector fields, enabling directional derivatives and feature smoothing.
- Low-frequency Laplacian eigenvectors provide globally consistent vector fields that capture graph structure and generalize grid axes for directional aggregation.
- The method mathematically generalizes CNNs by reproducing all radius-R convolutional kernels on n-dimensional grids and supporting reflection, rotation, and distortion of directions.
- DGN models theoretically and empirically enable efficient message passing across distant communities, counteracting over-smoothing.
- Relative improvements reached 8% on CIFAR10, 11-32% on ZINC, 0.8% on MolHIV, and 1.6% on MolPCBA across five standard datasets.
2 Theoretical development
The paper defines globally consistent directional message passing on graphs using vector fields, especially gradients of low-frequency Laplacian eigenvectors. This framework provides directional smoothing and derivatives, generalizes CNN convolutions on grids, improves long-range propagation, and exceeds 1-WL expressiveness.
- Vector fields in a graph: Directional vector fields weight graph edges by flow magnitude and orientation, enabling message passing along specified directions.A left-to-right grid flow assigns positive weights to left-to-right edges, negative weights to reverse edges, and zero weights to vertical edges.
- Data augmentation: Vector fields can encode prior directional knowledge, such as cardinal directions or rush-hour traffic flow, and can be transformed for reflection, rotation, and distortion augmentation.Transforming the field changes the aggregation kernel without modifying or preprocessing the input data.
- Directional smoothing and derivatives: Directional aggregation projects incoming messages onto a vector field to compute either smoothing or directional derivatives of node features.The weighted matrices B_av and B_dx implement these complementary low-pass and high-pass operations.
- Gradient of the Laplacian eigenvectors: Low-frequency Laplacian eigenvector gradients provide interpretable global directions that can guide aggregation and support efficient information transfer between distant nodes.Following the lowest non-trivial eigenvector direction reduces diffusion distance, while the resulting fields can counteract over-smoothing and over-squashing.
- Generalization of CNNs: On grid graphs, eigenvector-based directional aggregation generalizes CNNs by realizing any radius-R convolutional kernel in an n-dimensional lattice.The eigenvectors act analogously to Euclidean axes, and any radius-R kernel can be formed from directional aggregators and their compositions.
- Comparison to the Weisfeiler-Lehman (WL) test: DGNs using the mean aggregator, a directional aggregator from the first Laplacian eigenvector, and injective degree-scalers are strictly more powerful than the 1-WL test.This establishes greater discriminative expressiveness than ordinary GNNs under the stated theorem conditions.
3 Implementation
The implementation evaluates directional aggregation in multiple message-passing architectures, with optional edge features, degree scaling, and Laplacian-eigenvector fields.
- Experiments evaluate ZINC, CIFAR10, PATTERN, MolHIV, and MolPCBA using MAE, accuracy, ROC-AUC, and average precision.
- DGN is inserted into GCN-like and general MPNN architectures, with or without edge features.
- The approach has time complexity O(Em), matching PNA, where E is edges and m is aggregators.
- Degree scalers normalize or amplify each aggregator according to node degree relative to the training-set average.
- Directional aggregators use gradients of the first k Laplacian eigenvectors as vector fields, typically with k=1 or 2.
4 Results and discussion
Directional aggregators consistently improve benchmark performance, with especially strong gains on molecular datasets and CIFAR10. Kernel transformations can improve generalization, but excessive rotation or distortion reduces performance.
- Directional aggregators consistently boost simple, complex, and edge-aware models over the mean-aggregator baseline under matched budgets and hyperparameters.
- DGN outperforms previous models on PATTERN, where leading eigenvector flows correlate with community membership.
- Molecular datasets show significant gains with directional aggregators, especially the derivative aggregator Bdx, which can capture directional high-frequency signals.
- Positional encoding with the first two non-trivial eigenvectors shows no clear improvement on most datasets, whereas directional flows improve results with fewer parameters and less depth.
- DGN provides significant improvement across all fine-tuned benchmarks, with results averaged over repeated runs and compared against literature models.
- Figure 6 results are better than Figure 5 because Figure 5 uses a more exhaustive parameter search and adds PNA min/max aggregators.
- Randomly rotating or distorting kernels counteracts overfitting on a reduced CIFAR10 dataset and improves generalization.
5 Conclusion
The DGN method addresses several GNN limitations by introducing directional aggregation based on interpretable vector fields, while extending directional CNN properties to graphs. The paper combines theoretical claims about long-range connectivity and WL-test expressiveness with empirical support and identifies future directions for directional GNNs.
- DGN addresses the lack of anisotropy, low expressiveness, over-smoothing, and over-squashing in GNNs.
- Low-frequency Laplacian eigenvectors provide interpretable directional flows that support long-range connectivity and improved WL-test expressiveness.
- Future work includes hardening aggregators, boundary zero-padding, radius-R kernels, directional data augmentation, and improved selection of multiple directions.
- Vector-field aggregators weight neighbouring messages by their alignment with local directions, enabling directional smoothing, derivatives, and optional forward or backward propagation.
- Hardening the field with softmax or argmax can select a dominant neighbour instead of averaging many neighbours.
A.7 Extending the radius of the aggregation kernel
The appendix extends directional aggregation to radius-R kernels by composing walks across multiple directional fields. It reduces redundant parameterizations through reverse ordering, while preserving exact generalization on grid graphs and describing eigenvector-gradient normalization choices.
- The proposed radius-R kernel assigns different weights to subsets of nodes at distance R from a center node.
- The general kernel combines walks of at most R steps across n directional fields, with signs selecting forward or backward aggregation.
- Reverse ordering replaces permutation enumeration, reducing parameters while retaining grid-graph generalization rather than exact generalization for every graph.
- Gradient fields of Laplacian eigenvectors are normalized because eigenvector gradients become small near their extrema.
- Applying arcsine after maximum normalization makes eigenvector gradients more uniform, but the normalization is required because arcsine accepts inputs only in [−1, 1].
B.1 Benchmarks and datasets
The evaluation uses five standard graph benchmarks spanning molecular regression and classification, image classification, and synthetic node classification. Comparisons vary aggregation, architecture, parameter budget, tuning procedures, and dataset-specific assumptions.
- The benchmark suite includes ZINC, CIFAR10, PATTERN, MolHIV, and MolPCBA across regression, graph classification, and node classification tasks.
- ZINC predicts logP − SA, while CIFAR10 classifies images represented as approximately 100-node super-pixel graphs.
- PATTERN tests recognition of predetermined subgraphs through two-community node classification generated with Stochastic Block Models.
- Figure 5 comparisons vary only aggregation method and architecture width under a fixed parameter budget, using shared hyperparameters from prior work.
- For CIFAR10, eigenvectors cannot deterministically define the field because the first nontrivial Laplacian eigenvalue has multiplicity greater than one, so image-coordinate gradients are used.
B.2 Implementation and computational complexity
DGN adds eigenvector precomputation but retains linear-in-edges training complexity, with modest runtime trade-offs. Its directional computations also face scope boundaries for dynamic graphs and repeated Laplacian eigenvalues.
- Eigenvector precomputation using Lanczos has time complexity O(Ek), while training has aggregation complexity O(Em) and MLP complexity O(Nm).
- For dynamic graphs, changing edges require the Laplacian eigenvectors to be recomputed, although random-walk algorithms may estimate them efficiently for small changes.
- Equivariant directions from Laplacian eigenvectors require unique low-eigenvalue eigenspaces; repeated eigenvalues prevent this construction.
C.3 Proof of theorem 2.3 (Gradient steps reduce diffusion distance)
The proof shows that stepping from x in the direction of ∇φ1 reduces its diffusion distance to y after a sufficiently large time threshold. The reduction is proportional to e^-λ1.
- The diffusion-distance reduction is proportional to e^-λ1.
- The argument uses the continuous heat kernel, obtained by diagonalizing the heat-kernel operator.
- The distance condition is reformulated through an inequality whose bounds establish the required threshold.The proof states the equivalence and successive upper bounds leading to the condition dt(x′, y) < dt(x, y).
- A step from x along ∇φ1 yields dt(x′, y) < dt(x, y) when t exceeds a constant threshold.The proof introduces x′ as the node reached by one directional step and establishes the strict distance reduction for C ≤ t.
C.4 Proof for Lemma C.1 (Cosine eigenvectors)
The appendix characterizes Laplacian eigenvectors on lattice graphs through cosine eigenvectors inherited from path-graph Cartesian products. It then uses these axis-aligned eigenvectors to represent local convolution kernels with directional aggregators.
- Cosine eigenvectors: A lattice graph is the Cartesian product of path graphs, with vertices adjacent when they differ by one unit in exactly one coordinate.
- Cosine eigenvectors: Lattice Laplacian eigenvectors are tensor products that vary along one coordinate and remain constant along the others.The associated eigenvalues arise by summing the eigenvalues of the constituent path graphs.
- Directional kernel representation: On a path graph, any 1D convolution kernel of size 3 is a linear combination of Bav, Bdx, and the identity I.
- Directional kernel representation: The monotonicity of the first nonzero path eigenvector ensures the coefficient system for this representation has a solution.
- Directional kernel representation: Any radius-1 kernel on an n-dimensional lattice is a linear combination of Bav(φi), Bdx(φi), and I.
C.6 Proof for theorem 2.4 (Generalization radius-R convolutional kernel in a lattice)
The proof extends radius-1 directional kernel representations to arbitrary-radius kernels on lattice graphs. It constructs larger kernels by composing directional steps across coordinate fields and combining the resulting walks.
- General radius-R construction: For an n-dimensional lattice, any convolutional kernel of radius R can be realized by linear combinations of directional aggregation matrices and their compositions.
- General radius-R construction: The construction begins with a radius-1 kernel and adds all possible two-step positive and negative directional combinations for radius 2.
- General radius-R construction: The radius-R extension is obtained by combining aggregators that follow every allowed walk of at most R steps.
- Directional fields: A walk V records the number of forward or backward steps taken in each directional field, with total radius bounded by the walk length.For example, V = {3, 1, 0, −2} represents six steps across four fields.
C.7 Proof for theorem 2.5 (Comparison with 1-WL test)
The proof establishes that DGNs are at least as powerful as 1-WL and strictly more powerful by distinguishing a graph pair that 1-WL cannot separate. Directional aggregation based on the first Laplacian eigenvector produces the differing updates.
- Expressiveness comparison: DGNs using mean aggregation, a first-eigenvector directional aggregator, and injective degree-scalers are strictly more powerful than the 1-WL test.
- Expressiveness comparison: The mean aggregator with an injective degree-scaler makes DGNs at least as powerful as 1-WL.
- Separating graph pairs: DGNs are strictly stronger because they distinguish a graph pair that 1-WL cannot distinguish.
- Separating graph pairs: Directional smoothing or derivative aggregation based on the first Laplacian eigenvector gives the a-nodes different feature updates across the two graphs.