Source-linked AI summary
Directed Graph Convolutional Network
Zekun Tong, Yuxuan Liang, Changsheng Sun, David S. Rosenblum, Andrew Lim
TL;DR
Spectral-based GCNs are limited by their reliance on undirected graphs and first-order information. The paper introduces DGCN, which combines first- and second-order proximity to learn directed-graph representations while expanding the receptive field. Experiments on real-world semi-supervised classification tasks report improved performance and generalization against other models.
Problem
Spectral-based GCNs are limited to undirected graphs, and existing convolutions often capture only first-order information.
Method
DGCN extends spectral graph convolution to directed graphs by combining first- and second-order proximity.
Results
Experiments on semi-supervised classification across citation and co-purchase datasets demonstrate DGCN’s superiority over state-of-the-art methods.
Takeaways & Limitations
First- and second-order proximity can retain directed graph features, expand the convolution receptive field, and support effective graph representation learning.
Takeaways & Limitations
The fusion function and concatenation weights are selected manually, and future work targets automatic fusion, mini-batch training, and inductive learning.
Abstract
from arXiv · showhide
Graph Convolutional Networks (GCNs) have been widely used due to their outstanding performance in processing graph-structured data. However, the undirected graphs limit their application scope. In this paper, we extend spectral-based graph convolution to directed graphs by using first- and second-order proximity, which can not only retain the connection properties of the directed graph, but also expand the receptive field of the convolution operation. A new GCN model, called DGCN, is then designed to learn representations on the directed graph, leveraging both the first- and second-order proximity information. We empirically show the fact that GCNs working only with DGCNs can encode more useful information from graph and help achieve better performance when generalized to other models. Moreover, extensive experiments on citation networks and co-purchase datasets demonstrate the superiority of our model against the state-of-the-art methods.
1 INTRODUCTION
Existing spectral-based GCNs are restricted to undirected graphs and typically capture only first-order information. DGCN addresses these limitations by combining first- and second-order proximity on directed graphs, with experiments reporting improved effectiveness and generalization.
- Motivation: Spectral-based GCNs require undirected graphs, so symmetrizing directed graphs loses directional and temporal structure.In citation graphs, later papers can cite earlier papers, but the reverse relation does not hold.
- Motivation: Existing spectral-based convolutions generally use only 1-hop features, missing legitimate relationships represented through shared neighbors rather than direct links.The paper gives social-network communities as an example where shared interests need not produce direct contact.
- Approach: Second-order proximity complements first-order proximity by retaining directional features and expanding the graph convolution receptive field.Nodes can have second-order proximity when they share common neighbors, even without a direct path between them.
- Contribution: DGCN is a spectral-based directed-graph model that uses first- and second-order proximity to extract graph information.The model is presented as the first attempt to generalize spectral-based GCNs to directed graphs.
- Evaluation: Experiments on semi-supervised classification across real-world datasets validate proximity effectiveness and improvements over other models.The introduction also reports feature and label efficiency and generalization capability.
2 PRELIMINARIES
The paper formalizes directed weighted graphs, proximity orders, smoothness measures, and semi-supervised node classification. First- and second-order edges define the structural information used to evaluate surrounding features and labels.
- Graph preliminaries: A directed graph consists of vertices and ordered edges, with positive edge weights representing weighted connections.Undirected graphs are treated as pairs of opposite directed edges with equal weights, and only non-negative weights are considered.
- Smoothness measures: Feature Smoothness measures how much surrounding feature information is obtained over the normalized node-feature space.Its formulation uses Manhattan distance, feature dimension, and node features.
- Smoothness measures: Label Smoothness evaluates whether surrounding-node information is useful by measuring consistency between current and neighboring labels.Labels are considered consistent when the corresponding vertices have the same label.
- Proximity definitions: First-order proximity is a direct edge, while second-order proximity arises when two vertices share an incoming or outgoing neighbor.The combined edge set contains both first- and second-order edges.
- Task: Semi-supervised node classification predicts unlabeled node labels from labeled nodes, node features, and the graph adjacency matrix.The labeled subset is generally much smaller than the full vertex set.
3 UNDIRECTED GRAPH CONVOLUTION
Classical spectral graph convolution relies on Laplacians for undirected graphs and uses localized polynomial filters. Relaxing directed graphs into symmetric forms enables convolution but removes directional structure, motivating a directed alternative.
- Spectral formulation: Spectral graph convolution on an undirected graph uses the Laplacian eigendecomposition to define filtering in the Fourier domain.The graph Laplacian is formed from the degree and adjacency matrices.
- Polynomial approximation: Chebyshev-polynomial approximations reduce computation while integrating node features within a K-hop neighborhood.The scaled Laplacian and recursive Chebyshev polynomials define the localized filter.
- GCN approximation: The GCN simplifies Chebyshev convolution through a first-order approximation and a renormalization trick.This produces the standard propagation operation used by GCNs.
- Layer operation: The final convolution transforms C-dimensional node features using a filter-parameter matrix into F-dimensional convolved representations.The output is denoted Z′.
- Directed-graph limitation: Applying these derivations to directed graphs requires symmetrization, which makes spectral convolution possible but cannot represent the original directional structure.In citation networks, symmetrization removes the temporal restriction that earlier papers cannot cite later ones.
- Transition to DGCN: The paper therefore proposes a spectral GCN for directed graphs that leverages first- and second-order proximity.This proposal is introduced as the solution to the information loss caused by undirected relaxation.
4 THE NEW MODEL: DGCN
DGCN extends spectral graph convolution to directed graphs by combining first-order and direction-sensitive second-order proximity. It uses these proximity signals to preserve directed structure while expanding the convolution receptive field.
- DGCN architecture: DGCN is a spectral-based GCN for directed graphs that leverages first- and second-order proximity.The model uses a multi-layer propagation rule with normalized proximity matrices, a fusion function, shared trainable weights, and an activation function.
- First- and second-order proximity: First-order proximity captures local pairwise relationships between vertices, while second-order proximity connects nodes through shared neighbors.Second-order in-degree proximity reflects similarity in incoming neighborhoods, whereas second-order out-degree proximity reflects similarity in outgoing neighborhoods.
- First- and second-order proximity: The first-order matrix is symmetric, so it can lose directed information; second-order in- and out-degree proximities restore direction-sensitive structure.The in-degree and out-degree proximity matrices are themselves symmetric because their shared-neighbor relationships are pairwise.
- Proximity convolution: First-order proximity supplies a 1-hop-like receptive field, whereas second-order proximity supplies a 2-hop-like receptive field.The model therefore extracts features from both directly adjacent nodes and second-order neighbors.
- Fusion operation: DGCN fuses first-order, second-order in-degree, and second-order out-degree convolution outputs to retain directed structure and surrounding information.The fusion can use normalization, summation, or concatenation; concatenation performed best in practice, with weights controlling the relative importance of the proximities.
- Generalization: The proximity matrices can replace the original adjacency-based operation in other spectral GCN models, supporting generalization beyond DGCN.The paper reports that this replacement can simplify SGC while improving its accuracy.
5 EXPERIMENTS
Experiments evaluate DGCN on citation and co-purchase networks, comparing it with spectral- and spatial-based GNN baselines. DGCN generally achieves strong classification and improves generalized SGC through first- and second-order proximity, while depth and training-size studies reveal scope-dependent behavior.
- Baseline comparison: DGCN achieves state-of-the-art results on all datasets except Cora-Full, including the directed Cora-ML and CiteSeer datasets and undirected DBLP and PubMed datasets.On Amazon-Photo and Amazon-Computers, gains over GCN are not significant because DGCN uses one convolutional layer while GCN uses two.
- Proximity evaluation: Second-order proximity raises CiteSeer feature smoothness from 8.719 × 10−4 to 54.720 × 10−4 and label smoothness from 0.4893 to 0.5735.Across the other datasets, feature smoothness also increases substantially, while label smoothness decreases slightly.
- Generalization to SGC: Generalized SGC with concatenated first- and second-order proximity outperforms original SGC on all datasets, improving classification accuracy and reducing standard deviations.The generalized model replaces SGC’s original K-th power adjacency matrix with the concatenated proximity matrices.
- Model depth: 1- or 2-layer DGCN models obtain the best results on the tested datasets, while deeper models do not improve test accuracy because of overfitting.The depth experiment uses 10 labeled training nodes per class, 500 validation nodes, and the remaining nodes for testing.
- Weight selection: Accuracy decreases at boundary values of α and β and increases when the first- and second-order proximity weights are close.The weights control the contributions of first- and second-order proximity when they are concatenated.
- Training-set size: With small training sets, the evaluated methods perform similarly, whereas accuracy improves substantially as the number of labeled nodes increases.DGCN performs below GCN on CiteSeer and below GAT on DBLP in the reported training-size experiment.
6 RELATED WORK
Related work situates DGCN among methods using second-order proximity and methods expanding graph-convolution receptive fields through K-hop or multi-scale adjacency powers.
- First- and Second-order Proximity: Earlier work uses second-order proximity to extract information from directed graphs, including hub-and-authority representations and graph-embedding models.These approaches motivate using shared-neighbor structure beyond direct links.
- K-hop Method: K-hop methods expand receptive fields by aggregating information from higher-order neighbors or using different powers of adjacency matrices.ChebyNets and N-GCN are cited as examples of this strategy.
7 CONCLUSION AND FUTURE WORK
The paper concludes that DGCN extends spectral graph convolution to directed graphs by combining first- and second-order proximity. It also identifies automatic fusion, mini-batch training, and inductive learning as future directions.
- Conclusion: DGCN applies spectral graph convolution to directed graphs while retaining directed features and expanding the convolution receptive field.The paper evaluates these properties through semi-supervised classification experiments on real-world datasets.
- Future work: Future work will seek principled automatic fusion of proximity matrices, mini-batch training for faster large-dataset training, and inductive-learning extensions.The current approach uses manually selected fusion functions and concatenation weights.
A REPRODUCIBILITY DETAILS
The paper provides implementation details intended to support reproducibility, including software, datasets, baseline settings, and computing hardware.
- Reproducibility setup: DGCN and baseline models were implemented with PyTorch 1 and DGL 0.3 and run on Ubuntu 16.04 using one NVIDIA GTX-2080Ti GPU and two Intel Xeon E5-2690 CPUs.The reproducibility materials include pseudocode, dataset information, and baseline settings.
A.1 DGCN pseudocode
The DGCN procedure takes graph structure, node features, nonlinear activation, and weight parameters as inputs, then outputs a predicted class matrix.
- DGCN uses adjacency matrix A, feature matrix X, nonlinear function σ, weight matrices Θ, and concat weights α and β.
- The procedure produces a predicted class matrix ˆY.
14 end
The method constructs normalized directed graph representations from feature propagation through the adjacency matrix and its incoming and outgoing variants.
- DGCN row-normalizes AF, ASin, and ASout to obtain DF, DSin, and DSout.
A.2 Datasets Details
The experiments use seven open-access datasets and compare DGCN with established graph-learning baselines under specified preprocessing and training settings.
- Datasets: Seven open-access datasets are used, with two unsplittable Cora-ML classes combined with their nearest class.
- Datasets: Label rate is defined as the fraction of training nodes per class, calculated using 20 labeled nodes per class.
- Baselines: The evaluated baselines are ChebNet, GCN, SGC, GraphSage, and GAT.
- Baselines: ChebNet uses Chebyshev polynomials to avoid Laplacian eigenvalue decomposition, while SGC removes nonlinear layers and collapses weight matrices.
- Baselines: GCN stacks first-order Chebyshev polynomials with nonlinear activation, GraphSage supports inductive node embedding, and GAT weights neighborhood nodes using attention.
- Experimental settings: Baseline models retain their original architectures and settings; GraphSage uses mean aggregation, with batch sizes of 512 on Amazon-Photo and Amazon-Computer and 16 elsewhere.