Abstract
Standard Graph Convolutional Networks (GCNs) typically treat edges as binary indicators or scalar weights, overlooking the rich, multi-dimensional information often present in real-world connections. We present GCN-LASE, a framework that incorporates vector-valued link attributes into the learning process. By utilizing tensor products to model interactions between node and link features, LASE captures complex relational contexts. Our approach, derived from graph kernel theory, introduces a modular architecture consisting of Gate, Amplifier, and Aggregator components. Experimental results on social, citation, and temporal networks demonstrate that GCN-LASE significantly outperforms traditional GCNs and GraphSAGE, particularly in scenarios where link attributes provide critical context.
Introduction
In graph-based machine learning, the focus has traditionally been on node features. However, in many domains, the relationships themselves carry significant data. A link in a social network might represent a family tie, a professional collaboration, or a casual acquaintance—each with distinct implications for information flow. Most existing GCN architectures simplify these links into binary values or single weights, losing the nuance of the underlying data.
What Problem Does This Paper Address?
The primary challenge lies in how to mathematically integrate multi-dimensional link attributes. Simple methods like concatenating link features to node features often fail to capture how a specific relationship type modifies the neighbor's influence.
As shown above, link attributes can represent diverse information, from content similarity in shopping networks to time-series data in temporal phone contact graphs. The authors seek a principled way to allow the network to "understand" the specific context of every connection.
Methods: The LASE Framework
The authors propose LASE (Link Attributes and Sampling Estimation), which introduces three key innovations to address the limitations of standard GCNs.
1. Neighbor Feature Tensors
Instead of additive or concatenative methods, LASE employs the tensor product of node and link features. This creates a "fully associated" feature representation that captures all bilinear combinations of attributes, ensuring that the interaction between the node's state and the link's type is explicitly modeled.
2. Kernel-Derived Architecture
The LASE architecture is grounded in established graph kernels, specifically Random Walk and Weisfeiler-Lehman kernels. This theoretical foundation leads to a modular design:
- Gate: Evaluates the overall influence or importance of a neighbor.
- Amplifier: Uses link information to element-wise modify neighbor node attributes, acting as a context-aware filter.
- Aggregator: Combines these modified neighbor embeddings into the target node's representation.
3. Min_Var Sampling
To maintain scalability on large graphs, LASE utilizes a "minimum variance" Monte Carlo sampling strategy. By calculating optimal sampling probabilities every $k$ batches, the model balances training efficiency with estimation accuracy, leading to more stable convergence than uniform sampling.
Key Insights
A critical finding is the failure of concatenation. As illustrated in the structural comparison above, models that simply append link features to node features cannot distinguish between different graph configurations where the same set of features is present but distributed differently across edges. The tensor product approach in LASE ensures the model can "see" the specific pairing of node and link attributes.
Furthermore, the authors demonstrate that temporal graphs can be effectively modeled by treating the time-series of connections as a vector attribute on a static edge, providing a powerful alternative to complex dynamic graph architectures.
Experimental Results
LASE was evaluated on four diverse datasets: Reddit (social), DBLP (citation), and Email/fmobile (temporal).
- Superior Accuracy: LASE-SAGE and LASE-RW consistently outperformed standard GCNs. On the
emaildataset, LASE-SAGE achieved a Micro-f1 score of 0.7310, compared to 0.6548 for GraphSAGE. - Robustness to Noise: Signal-to-Noise Ratio analysis confirmed that the model's performance is directly tied to the quality of link data, proving it successfully leverages the provided attributes.
Conclusion
GCN-LASE represents a significant step toward more expressive graph neural networks. By treating links as rich context rather than simple pipes, the model achieves state-of-the-art performance on complex, attribute-heavy graphs. While computational complexity remains a challenge for industrial-scale deployment, the use of tensor products and principled sampling offers a robust framework for future research in relational learning.
Summary updated