Source-linked AI summary
MotifNet: a motif-based Graph Convolutional Network for directed graphs
Federico Monti, Karl Otness, Michael M. Bronstein
TL;DR
Spectral graph CNNs are limited by their assumption of undirected graphs, while directed graphs require filters that can capture local orientation. MotifNet addresses this with motif-based graph filters and outperforms ChebNet on real directed-graph data with only a tiny parameter increase.
Problem
Spectral graph constructions assume undirected graphs, making directed graphs and oriented filters challenging to handle.
Method
MotifNet applies multivariate polynomial filters to motif-induced Laplacian matrices and uses attention to generalize graph CNN models.
Results
MotifNet-m consistently outperforms ChebNet across polynomial orders on the directed CORA citation network, with only a tiny increase in parameters.
Takeaways & Limitations
The reported experiments support motif-based graph convolutions as an effective approach for directed-graph learning on real data.
Takeaways & Limitations
The multivariate filter formulation can require an impractically large number of coefficients even for modest motif counts or polynomial degrees.
Abstract
from arXiv · showhide
Deep learning on graphs and in particular, graph convolutional neural networks, have recently attracted significant attention in the machine learning community. Many of such techniques explore the analogy between the graph Laplacian eigenvectors and the classical Fourier basis, allowing to formulate the convolution as a multiplication in the spectral domain. One of the key drawback of spectral CNNs is their explicit assumption of an undirected graph, leading to a symmetric Laplacian matrix with orthogonal eigendecomposition. In this work we propose MotifNet, a graph CNN capable of dealing with directed graphs by exploiting local graph motifs. We present experimental evidence showing the advantage of our approach on real data.
1. INTRODUCTION
Graph CNNs must address the lack of vector-space structure and shift-invariance in graph data, while existing spectral formulations are limited to undirected graphs. MotifNet addresses directed graphs using motif-based anisotropic filters and attention, with experiments on real data showing superior performance over previous approaches.
- Motivation: A central challenge in extending CNNs to graphs is the lack of vector-space structure and shift-invariance, requiring graph-specific convolutional building blocks.This challenge arises in applications including social network analysis and recommendation systems.
- Background: Existing graph CNN formulations comprise spatial approaches that construct local graph weights and spectral approaches that define convolution-like operations in the spectral domain.Spatial methods generalize pixel patches, whereas spectral methods use the analogy between graph-Laplacian eigenfunctions and the Fourier transform [5] [6] [10].
- Contribution: MotifNet introduces a graph CNN for directed graphs using anisotropic graph-filter bases built from local subgraph structures, or motifs.The method targets directed graphs through motif-based local structure.
- Contribution: Experimental validation on real data shows MotifNet achieves superior performance compared to previous approaches.The passage states the overall empirical advantage without reporting numerical results.
- Contribution: MotifNet incorporates attention to generalize some standard graph CNN models without significantly increasing model complexity.The attention mechanism is presented as part of the proposed architecture.
2. BACKGROUND
The background develops graph Fourier analysis from the symmetric Laplacian of weighted undirected graphs and reviews spectral graph CNNs. It then summarizes efficiency improvements from polynomial filters while noting limitations on community graphs with clustered eigenvalues.
- Graph Fourier analysis: For weighted undirected graphs, the symmetric normalized Laplacian has an orthonormal eigenbasis that supports Fourier decomposition of vertex functions.The graph Fourier transform is ˆf = Φ⊤f, with Laplacian eigenvectors serving as Fourier atoms.
- Spectral graph CNNs: Bruna et al. [5] used this spectral formulation to construct graph convolutional neural-network layers with learnable spectral multipliers and nonlinearities.The filters act diagonally in the graph Fourier domain, and the layer maps input channels to output channels.
- Spectral graph CNNs: Spectral CNNs can require O(n^2) computation because graph Fourier transforms entail dense n × n matrix multiplication.Spline filters parameterize spectral multipliers as τθ(λk) = Pp_{j=1} θjβj(λk).
- Polynomial spectral filters: Defferrard et al. introduced ChebNet, whose Chebyshev polynomial filters avoid eigendecomposition and reduce complexity to O(|E|), or O(n) for sparse graphs.The filters are computed through powers of the graph Laplacian using Chebyshev polynomials.
- Polynomial spectral filters: Kipf and Welling simplified ChebNet by using a first-order polynomial and Laplacian re-normalization, but ChebNet and GCN struggle with clustered eigenvalues typical of community graphs.Levie et al. [10] instead used rational filter functions based on the Cayley transform.
3. DEALING WITH DIRECTED GRAPHS
Spectral graph constructions assume undirected graphs because orthonormal Laplacian eigendecomposition requires symmetric adjacency, and their Laplacian filters are isotropic. Motif-based analysis addresses these limitations by using directed subgraph patterns to induce anisotropic, directionally preferred operators.
- Spectral constructions require symmetric adjacency for an orthonormal Laplacian eigendecomposition, so directed graphs violate a central assumption.
- The Laplacian is isotropic and lacks a preferred graph direction, while anisotropic oriented filters are harder to construct on general graphs than on manifolds.Chebyshev filters on a regular grid illustrate this isotropy through rotational invariance of the Laplacian.
- Motif analysis provides a workaround by representing meaningful directed connectivity patterns as small graph motifs.For a weighted directed graph G = {V, E, W}, the adjacency need not be symmetric, and the method considers a collection M1, . . . , MK of motifs.
- Each motif-associated adjacency acts anisotropically, establishing a preferred direction along structures associated with that motif.
- The paper uses thirteen 3-vertex graph motifs as its motif collection.
4. MOTIFNET
MotifNet constructs directed-graph convolutional filters from motif-induced adjacencies using multivariate polynomial filters of motif Laplacians. It addresses the resulting coefficient-growth problem through simplified motifs and defines ChebNet as a special case.
- 4. MOTIFNET: MotifNet uses multivariate degree-p polynomial filters over motif Laplacian matrices, including K^p products because these matrices generally do not commute.The non-commutativity of motif Laplacians requires products such as ˜∆k1 · · · ˜∆kp with kl ∈ {1, . . . , K}.
- 4. MOTIFNET: The full polynomial has 1+Kp+1 coefficients, making it impractically large even for modest motif counts K or degree p.This coefficient-growth issue motivates the two simplifications studied next.
- 4. MOTIFNET: Attention scores from a first-order MotifNet identify 7 of 15 possible motifs as relevant for classifying vertices in directed CORA.Dark colors indicate high probabilities and bright colors low probabilities in the visualization.
- 4. MOTIFNET: The first simplification retains only K = 2 motifs representing incoming and outgoing edges from each vertex, with Kp + 1 coefficients constrained by 0 ≤ αi,j ≤ 1.The coefficients are Θ = (θ0, . . . , θp, α1,1, . . . , αK,p).
- 4. MOTIFNET: MotifNet applies the simplified multivariate polynomial in graph convolutional layers, while ChebNet is recovered using one undirected-graph Laplacian and a univariate polynomial.The layers map q′ input channels to q output channels through the polynomial PΘ.
5. EXPERIMENTAL EVALUATION
The evaluation uses semi-supervised paper classification on the directed CORA citation network, comparing ChebNet with MotifNet variants. MotifNet-m consistently outperforms ChebNet across polynomial orders while requiring only a tiny parameter increase.
- 5. EXPERIMENTAL EVALUATION: The models classify 19,793 CORA papers into 70 categories using 130 PCA-reduced features in a semi-supervised split with 10% training, validation, and testing vertices.CORA edges encode citations, and the original paper representations contain 8,710 TF-IDF features before PCA.
- 5. EXPERIMENTAL EVALUATION: The comparison includes ChebNet on undirected and directed adjacency matrices, plus MotifNet-m and MotifNet-d using simplified multivariate matrix polynomials.The architectures use two convolutional layers and evaluate motif subsets including M5, M8, M9, U, M_in, and M_out1.
- 5. EXPERIMENTAL EVALUATION: MotifNet-m consistently outperforms ChebNet across polynomial orders, with only a tiny increase in parameters.The comparison is reported for CORA classification in Figures 5–6, while Table 1 quantifies parameter requirements.
- 5. EXPERIMENTAL EVALUATION: Motif 1M10 was excluded from the final architecture because its motif adjacency matrix was dense.The final motif selection retained M5, M8, M9, U, M_in, and M_out1.