MotifNet: a motif-based Graph Convolutional Network for directed graphs
MotifNet employs motif-based multivariate polynomial filters to handle directed graphs, outperforming spectral methods on node classification tasks.
Key Findings
Methodology
MotifNet constructs motif-induced adjacency matrices capturing local directed structures, then defines non-symmetric Laplacians. It employs multivariate polynomial filters combined with an attention mechanism to select relevant motifs, enabling effective modeling of directionality. The approach integrates multiple motifs (e.g., 13 triplet motifs) into a polynomial filter framework, allowing flexible, expressive convolutional layers. Experiments on the CORA dataset with semi-supervised node classification demonstrate that MotifNet surpasses ChebNet (accuracy 60.0%) with 62.3%, using only a slight increase in parameters (~1%). The model employs two convolutional layers, regularization, and Adam optimization, validating the importance of local motifs in directed graph learning.
Key Results
- On CORA, MotifNet-m with p=3 achieved 62.3% accuracy, outperforming ChebNet (60.0%). Incorporating 13 motifs improved stability and performance across polynomial orders. The model parameters increased marginally (~1%), maintaining training efficiency. Ablation studies confirmed that motif adjacency matrices and multivariate filters are crucial for performance gains. The approach effectively captures local directed structures, especially in community-rich graphs, demonstrating robustness and scalability.
- MotifNet-d (using only in/out edges) achieved 63.0% accuracy, outperforming baseline models, highlighting the significance of motif-based adjacency in encoding directionality. The multi-motif polynomial filters significantly enhanced expressiveness, especially in graphs with clear community or hierarchical structures. The experimental results validate the hypothesis that local motifs serve as powerful structural priors for directed graph learning.
- Ablation experiments show that removing motif adjacency or simplifying polynomial filters reduces accuracy, emphasizing the synergy between local motifs and polynomial filtering. The models trained efficiently on GPU, with parameters comparable to ChebNet, and demonstrated strong generalization across different polynomial orders and motif subsets.
Significance
This work advances spectral graph neural networks by overcoming the symmetry constraint of traditional Laplacians, enabling effective modeling of directed graphs. By leveraging local motifs, it captures directionality and complex local structures, addressing a fundamental limitation in existing methods. The approach offers a flexible, scalable framework applicable to social, citation, and biological networks, where directionality is crucial. It bridges the gap between spectral theory and real-world directed data, opening new avenues for research and applications in graph-based learning.
Technical Contribution
MotifNet introduces a novel motif-based adjacency construction, enabling non-symmetric Laplacians that encode directionality. It develops multivariate polynomial filters over multiple motif Laplacians, controlled via attention mechanisms, to enhance local structure modeling. The architecture generalizes ChebNet by incorporating multiple motifs and higher-order polynomials, providing a richer, more expressive convolutional framework. Theoretical analysis confirms improved spectral resolution and stability, while practical implementation demonstrates efficiency and scalability.
Novelty
This is the first spectral GNN framework explicitly designed for directed graphs using motif-induced adjacency matrices. It innovates by integrating multiple local motifs into multivariate polynomial filters, capturing complex directional patterns. Unlike prior methods limited to undirected graphs, MotifNet explicitly models local directed structures, offering a new paradigm for graph convolutional learning. Its combination of motif analysis, attention, and polynomial filtering sets it apart as a pioneering approach.
Limitations
- Model performance depends on the predefined set of motifs; missing critical motifs may limit effectiveness. Constructing motif adjacency matrices can be computationally intensive for large graphs, impacting scalability. The approach's effectiveness on highly noisy or heterogeneous graphs remains to be thoroughly tested. Additionally, the selection of motifs and polynomial order requires careful tuning, which may limit automatic generalization.
- Current experiments are limited to citation networks; broader validation on diverse real-world datasets is necessary. The complexity of multivariate polynomial filters may lead to overfitting if not properly regularized. Future work should focus on automatic motif discovery, reducing computational costs, and extending to dynamic or multi-relational graphs.
Future Work
Future directions include developing methods for automatic motif learning to adaptively identify relevant local structures, reducing reliance on predefined motifs. Extending the framework to dynamic graphs will enable modeling temporal evolution of directed relationships. Improving computational efficiency, especially for large-scale graphs, through approximation or sampling techniques is also a priority. Additionally, integrating attention mechanisms more deeply into the motif selection process and exploring multi-relational or heterogeneous networks will broaden the applicability of MotifNet.
AI Executive Summary
In recent years, graph neural networks (GNNs) have revolutionized the analysis of structured data, with spectral methods like ChebNet and GCN achieving notable success. However, these approaches inherently assume undirected graphs, relying on symmetric Laplacians that cannot encode the directionality crucial in many real-world networks such as citation, social, and biological graphs. This limitation has hindered the ability of spectral GNNs to fully leverage the rich information embedded in directed relationships.
MotifNet addresses this challenge by introducing a motif-based framework that captures local directed structures through motif-induced adjacency matrices. By analyzing small, meaningful subgraphs (motifs), the method constructs non-symmetric Laplacians that preserve directionality. The core innovation lies in defining multivariate polynomial filters over multiple motif Laplacians, combined with an attention mechanism to select the most relevant motifs dynamically. This design allows the network to model complex local patterns and directional dependencies effectively.
Experimental validation on the CORA citation network demonstrates the superiority of MotifNet over traditional spectral methods. With an accuracy of 62.3% using a polynomial order of 3, it surpasses ChebNet's 60.0%, while maintaining parameter efficiency. The results highlight the importance of local motifs in capturing the nuanced structure of directed graphs. The approach's flexibility and scalability suggest broad applicability across various domains involving directed data.
This work significantly advances spectral graph learning by overcoming the symmetry constraint, offering a powerful tool for analyzing complex, directed networks. Its implications extend to improving community detection, influence modeling, and recommendation systems, where directionality plays a key role. Despite current limitations in motif selection and computational costs, future research on automatic motif discovery and large-scale optimization promises to further enhance the framework's potential.
Deep Dive
Abstract
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.