Learnable Path-Complex Features and Unified Path–Cellular Message Passing for Link Prediction

Two small but targeted modifications to Path Complex Networks: a position-aware learnable cell initialization that strictly subsumes the deterministic scatter-sum, and a unified path+cellular complex in which path-cells and ring-cells coexist and communicate through shared edge boundaries.

Download PDF View Code

Contents

• Introduction
• Preliminaries
• Path complexes
• Relations between cells
• Deterministic initialization
• Link prediction
• Method
• Learnable init
• Unified complex
• Theoretical results
• Message passing
• Decoder
• Experiments
• Setup
• Ablations
• Computational analysis
• Discussion
• Related work
• Conclusion
• Appendix: Proofs
• Appendix: Message-passing formula
• Appendix: Experiment details

Abstract

Path Complex Networks (PCN) generalize simplicial and cellular message-passing schemes by lifting a graph to its path complex and exchanging messages between elementary $k$-paths through boundary, co-boundary, and upper/lower-adjacency relations. In the original formulation, the feature of a $k$-cell $(v_0, \ldots, v_k)$ is a deterministic scatter-sum (or scatter-mean) of its constituent node features, discarding both the ordering along the path and any learnable capacity at the lifting step. Moreover, PCN commits to a single topological lift—paths, cliques, or rings—so the model cannot simultaneously exploit the complementary inductive biases offered by different cell types. We address both limitations in the context of transductive link prediction. First, we introduce a position-aware learnable feature initialization in which each position along a $k$-cell receives its own linear map, yielding order-sensitive path features at no asymptotic cost. We prove that this initialization strictly subsumes the deterministic scatter-sum. Second, we construct a unified path + cellular complex in which path-cells and ring-cells coexist at the same dimension and communicate through shared edge boundaries, so that a triangle $ABC$ is simultaneously a path $A{\to}B{\to}C$ and a 3-cycle without duplicating adjacency bookkeeping. We show that the isomorphism test induced by message passing on the unified complex (which we call U-PWL) is at least as powerful as both PWL and CWL($k$-IC), giving our architecture the theoretical expressivity of path-based and ring-based lifts simultaneously. We evaluate both contributions on Cora link prediction, ablating (i) deterministic vs. learnable initialization and (ii) path-only vs. unified complexes across 10 seeds per configuration, and we analyze the incurred lifting and message-passing cost both analytically and empirically.

Introduction

Graph neural networks (GNNs) that rely on the 1-Weisfeiler–Lehman (1-WL) update rule are fundamentally limited in their ability to distinguish non-isomorphic graphs . Higher-order topological GNNs escape this upper bound by lifting the graph to a richer combinatorial object—a simplicial complex , a regular cell complex , or a path complex —and running message passing over its cells. Each lift carries a different inductive bias: simplicial complexes privilege cliques, regular cell complexes privilege induced cycles, and path complexes privilege simple paths and therefore impose no structural assumption at all. For link prediction, however, the closed-neighborhood structure of a candidate edge $(u, v)$—how $u$ and $v$ co-participate in short cycles—is precisely the signal a model needs, and pure-path lifts discard that signal by construction.

Path Complex Networks (PCN) are attractive precisely because paths exist in every connected graph, but the published formulation leaves two degrees of freedom unused. First, cell features at dimension $k \geq 1$ are initialized by a deterministic scatter-sum of node features. Because summation is symmetric under permutation, the initial feature of the elementary path $A{\to}B{\to}C$ is identical to that of $C{\to}B{\to}A$, which is counterintuitive for an object whose defining property is an ordering of its vertices. Second, the lift is monolithic: one picks paths or rings or cliques. In practice, however, the same substructure—say a triangle—is a clique, a 3-cycle, and a path of length two simultaneously, and a model with access to all three views should, in principle, be strictly more expressive than any single one of them. This problem is especially pronounced for link prediction: the features that drive prediction (common neighbors, short cycles, triangle count) are expressed naturally in terms of ring-cells, while the features that drive graph-classification performance in PCN (long open paths) are expressed naturally in terms of path-cells.

Figure 1. (a) Original graph. (b) Simplicial complex arising from the graph: one 2-simplex, four 1-simplices, and four 0-simplices. The regular cell complex coincides with the simplicial complex in this case. (c) Simple-path spaces $\mathcal{S}_2$ and $\mathcal{S}_3$ corresponding to the path complex arising from the graph. Elementary paths of $\mathcal{S}_0$ and $\mathcal{S}_1$ coincide with 0-cells and 1-cells. Figure reproduced from .

We propose two small but targeted modifications to PCN.

1. Learnable, position-aware cell initialization. For an elementary $k$-path $(v_0, \ldots, v_k)$ we learn $k+1$ linear maps $W_0^{(k)}, \ldots, W_k^{(k)}$, one per position, and define the initial feature as $h_\sigma^{(0)} = \sum_{i=0}^{k} W_i^{(k)} x_{v_i}$. Node features thus enter the path-complex through a learned, ordered transform rather than a symmetric aggregation.
2. Unified path + cellular complex. We build a single complex in which path-cells and ring-cells coexist at dimension two, share the same edge identifier map, and communicate through their shared edges during message passing. A triangle therefore sends messages as a ring-cell and simultaneously appears as a path-cell; the two views are fused downstream through the dim-1 edges they both bound.

Both modifications are drop-in: the message-passing layer is unchanged, and the per-cell feature dimension is unchanged. We evaluate on Cora link prediction in the transductive setting of , reporting mean $\pm$ standard deviation of test ROC-AUC over 10 seeds for four configurations: (path, deterministic), (path, learnable), (unified, deterministic), (unified, learnable).

Contributions. Our work (i) identifies two underused degrees of freedom in the PCN lifting step—position order and cell-type multiplicity—and (ii) provides lightweight, backward-compatible modifications that address both. We prove that the position-aware initialization strictly subsumes the deterministic scatter-sum used by , and that the unified lift (U-PWL) inherits the theoretical guarantees of both PWL and CWL($k$-IC) . We validate the theory with an ablation study on Cora link prediction, and we analyze the computational overhead of both modifications analytically and empirically.

Preliminaries

Path complexes

Given a finite graph $G = (\mathcal{V}, \mathcal{E})$, a simple path of length $k$ is an ordered tuple $(v_0, \ldots, v_k)$ of distinct vertices with $\{v_i, v_{i+1}\} \in \mathcal{E}$ for all $0 \leq i < k$. Following , the set $P_k(G)$ of all such paths, together with boundary maps $\partial$ defined by deletion of the leftmost or rightmost vertex, forms a path complex.

Definition 1 (Elementary $p$-path). Given a finite non-empty vertex set $\mathcal{V}$, an elementary $p$-path on $\mathcal{V}$ is any sequence of vertices $e_{i_0 \ldots i_p}$ with length $p + 1$.

Definition 2 (Boundary operator). The boundary operator on elementary $p$-paths is defined as \partial \, e_{i_0 \ldots i_p} = \sum_{q=0}^{p} (-1)^q e_{i_0 \ldots \hat{i}_q \ldots i_p}, where $\hat{i}_q$ indicates removal of the index $i_q$ from the sequence.

Message passing in PCN operates over $P_0(G) \cup P_1(G) \cup \cdots \cup P_K(G)$ via boundary, co-boundary, and upper/lower-adjacency relations between elementary paths, in direct analogy with MPSN and CWN .

Figure 2. Examples of path complexes arising from (a) a simple path of length three and (b) a ring of size four. Blue arrows denote upper-adjacency; orange arrows denote boundary relations. Figure reproduced from .

Relations between cells

For a path complex $P$ and cells $\sigma, \tau \in P$, the relations used for message passing are:

• Boundary $\mathcal{B}(\sigma) = \{\tau \mid \tau \prec \sigma\}$.
• Co-boundary $\mathcal{C}(\sigma) = \{\tau \mid \sigma \prec \tau\}$.
• Upper-adjacent neighborhood $\mathcal{N}_\uparrow(\sigma) = \{\tau \mid \exists\,\delta:\; \sigma \prec \delta \wedge \tau \prec \delta\}$.
• Lower-adjacent neighborhood $\mathcal{N}_\downarrow(\sigma) = \{\tau \mid \exists\,\delta:\; \delta \prec \sigma \wedge \delta \prec \tau\}$.

As proven in , PWL with update rule $\mathrm{Hash}(c_\sigma^t, c_\mathcal{B}^t(\sigma), c_\uparrow^t(\sigma))$ is as powerful as PWL with the generalized update rule that also includes co-boundary and lower-adjacent messages. We adopt the former throughout.

Deterministic feature initialization in PCN

In the public PCN implementation , the feature of an elementary $k$-path at the input layer is

h_\sigma^{(0)} = \bigoplus_{v \in \sigma} x_v, \qquad \sigma = (v_0, \ldots, v_k),

where $\oplus \in \{\text{sum}, \text{mean}\}$ is a permutation-invariant aggregator and $x_v$ is the input feature of vertex $v$. We refer to this as the deterministic init. The expression is symmetric under any permutation of $(v_0, \ldots, v_k)$, so path orientation is lost at initialization and cannot be recovered by subsequent layers that operate only on $h_\sigma^{(0)}$.

Link prediction

We consider the transductive link-prediction setting of . Given a graph $G = (\mathcal{V}, \mathcal{E})$, a fraction of edges is held out for validation and test, and the model is trained to discriminate observed edges from sampled negatives. A graph encoder $f_\theta: \mathcal{V} \to \mathbb{R}^d$ produces a node embedding $h_v = f_\theta(v)$, and a decoder $g_\phi: \mathbb{R}^d \times \mathbb{R}^d \to [0, 1]$ produces an edge score $\hat{y}_{uv} = g_\phi(h_u, h_v)$. Throughout we use a dot-product decoder $\hat{y}_{uv} = \sigma(h_u^\top h_v)$ and binary cross-entropy loss, evaluated by ROC-AUC on the held-out edges.

Method

Learnable position-aware initialization

We replace the deterministic init with

h_\sigma^{(0)} = \sum_{i=0}^{k} W_i^{(k)} \, x_{v_i}, \qquad \sigma = (v_0, \ldots, v_k),

where $W_i^{(k)} \in \mathbb{R}^{d \times d_\text{in}}$ is a learnable linear map specific to the pair $(k, i)$ of dimension and position. Asymptotically the cost of the learnable init is identical to the deterministic one: each node contributes exactly once to the feature of each cell that contains it, and the only change is that the contribution is multiplied by a position-specific matrix before being accumulated.

Proposition 1. When $W_i^{(k)} = W$ for all $(k, i)$, the learnable init reduces to $W \sum_{i=0}^{k} x_{v_i}$, which is a linear projection of the deterministic scatter-sum. Hence any model built on top of the deterministic init is realizable by a model built on top of the learnable init; the converse does not hold.

Theorem 1. There exist a graph $G$ and elementary paths $\sigma, \sigma' \in P_k(G)$ which are equal as unordered multi-sets of vertices but differ as ordered tuples, such that the learnable init can assign them distinct initial features, whereas the deterministic init cannot.

A proof appears in Appendix A.1. The practical implication is that the learnable init breaks orientation symmetry at time step $t = 0$; any information that depends on the ordering of vertices along a path is thus available to all subsequent message-passing layers, rather than being filtered out irretrievably at initialization.

Unified path–cellular complex

Let $P_k(G)$ denote the set of simple $k$-paths of $G$ and $R(G)$ the set of induced cycles up to length $L$. We build a unified complex $\mathcal{C}(G)$ with cells

\mathcal{C}_0 = \mathcal{V}, \quad \mathcal{C}_1 = P_1(G), \quad \mathcal{C}_2 = P_2(G) \cup R(G), \quad \mathcal{C}_k = P_k(G) \ \text{for } k \geq 3.

The dim-0 and dim-1 identifier maps are shared across path-cells and ring-cells—edges are canonicalized to sorted tuples—so a ring-cell and a path-cell that share an edge point to the same edge identifier. Boundary extraction branches on cell type: path-cells use the left/right-deletion rule from §2.1, and ring-cells use the standard CW boundary map that returns every edge of the cycle. Upper and lower adjacencies are then computed by the existing PCN routine on the combined boundary tables, so messages flow seamlessly between a ring-cell and a path-cell that happen to share an edge.

Figure 3. The unified path + cellular complex on a small graph. At dimension two, the triangle $ABC$ appears simultaneously as a ring-cell and as a path-cell $A{\to}B{\to}C$. Both cells share the edge-cells $AB$ and $BC$; the ring-cell additionally shares $AC$. Because messages flow between any two dim-2 cells that share a dim-1 boundary, the ring and path views of the triangle communicate during upper- and lower-adjacency message passing.

Why this helps link prediction. Link prediction rewards models whose node embeddings capture closed-neighborhood structure: a pair $(u, v)$ is more likely to be linked when $u$ and $v$ participate in short cycles. Path-cells expose only open neighborhoods; ring-cells expose closed ones. Since cycles of length at most $L$ in Cora are overwhelmingly short, adding ring-cells to a path complex injects a targeted topological signal that paths alone do not carry.

Theoretical results

We establish that the isomorphism test induced by color refinement on the unified complex—which we call U-PWL—inherits the expressivity of both PWL and CWL($k$-IC) .

Theorem 2. U-PWL is at least as powerful as PWL at distinguishing non-isomorphic graphs.

Theorem 3. U-PWL is at least as powerful as CWL($k$-IC) with maximum dimension 2 at distinguishing non-isomorphic graphs.

Combining the two theorems and the result of that PWL is at least as powerful as CWL($k$-IC) with maximum dimension 2, we obtain:

Corollary 1. U-PWL is strictly more powerful than 1-WL at distinguishing non-isomorphic graphs. Moreover, U-PWL is not less powerful than 3-WL.

Proofs of Theorems 2 and 3 appear in Appendix A.2 and Appendix A.3; the proof of Corollary 1 is immediate from Theorems 2–3 together with prior results by and .

Message passing

Following , we update the feature of a cell $\sigma$ by aggregating boundary and upper-adjacent messages:

m_\mathcal{B}^{(t+1)}(\sigma) = \mathrm{AGG}_{\tau \in \mathcal{B}(\sigma)} \left( M_\mathcal{B}(h_\sigma^{(t)}, h_\tau^{(t)}) \right), m_\uparrow^{(t+1)}(\sigma) = \mathrm{AGG}_{\tau \in \mathcal{N}_\uparrow(\sigma), \delta \in \mathcal{C}(\sigma, \tau)} \left( M_\uparrow(h_\sigma^{(t)}, h_\tau^{(t)}, h_\delta^{(t)}) \right), h_\sigma^{(t+1)} = \mathrm{UP}\left( h_\sigma^{(t)}, m_\mathcal{B}^{(t+1)}(\sigma), m_\uparrow^{(t+1)}(\sigma) \right),

where $M_\mathcal{B}, M_\uparrow$, and $\mathrm{UP}$ are learnable functions realized by multi-layer perceptrons (MLPs). In the unified complex, the boundary and adjacency sets include ring-cells alongside path-cells, but the update rule itself is unchanged.

Link-prediction decoder

After $T$ message-passing layers, we extract node embeddings $h_v = h_\sigma^{(T)}$ for all $\sigma \in \mathcal{C}_0$ and score a candidate edge $(u, v)$ by a dot-product decoder:

\hat{y}_{uv} = \sigma\left( h_u^\top h_v \right),

where $\sigma$ is the logistic sigmoid. Training minimizes binary cross-entropy over sampled positive and negative edges.

Experiments

We evaluate our two contributions on Cora link prediction . Cora is a citation network with 2,708 nodes and 5,429 undirected edges; each node is a scientific publication with a 1,433-dimensional bag-of-words feature vector and a class label in one of seven research areas. We do not use the class labels. Detailed hyperparameter settings and an extended ablation on individual modifications appear in Appendix B.

Setup

We follow the transductive link-prediction protocol of : edges are split 85/5/10 into train/validation/test with an equal number of sampled negatives per split. The path complex (or unified complex) is built from training message-passing edges only, so there is no leakage of validation or test edges into the topology. All models use a 2-layer PCN encoder with hidden dimension 64, dropout 0.3 applied before the final linear layer, batch normalization, a dot-product decoder, and Adam with learning rate 0.01 and ReduceLROnPlateau scheduling (patience 20, decay rate 0.5, minimum learning rate $10^{-5}$). Each run is 200 epochs with early stopping on validation AUC. We report mean $\pm$ standard deviation over 10 seeds ($0, \ldots, 9$) and adopt the model checkpoint from the best validation epoch.

For the unified complex, the maximum ring size is set to $L = 7$, which is the default cutoff used by on small molecular graphs and which we found to be a reasonable compromise between topological coverage and lifting cost on Cora.

Ablations

Table 1. Cora link-prediction ROC-AUC (mean $\pm$ standard deviation over 10 seeds). Rows correspond to the four configurations obtained by crossing the lift (path vs. unified path + cellular) with the cell-feature initialization (deterministic scatter-sum vs. position-aware learnable). Bold indicates the best result in each column.

Complex	Init	Val AUC	Test AUC
Path	Deterministic	$0.7344 \pm 0.0274$	$0.7113 \pm 0.0239$
Path	Learnable	$0.7354 \pm 0.0230$	$0.7123 \pm 0.0164$
Unified	Deterministic	$\mathbf{0.7366 \pm 0.0270}$	$\mathbf{0.7132 \pm 0.0165}$
Unified	Learnable	$0.7335 \pm 0.0213$	$0.7111 \pm 0.0175$

Table 1 reports the four configurations. The (path, deterministic) baseline achieves test AUC $0.7113 \pm 0.0239$, consistent with the fact that PCN was not designed for link prediction and a pure-path lift provides little closed-neighborhood signal. Switching to the learnable initialization alone (row 2) yields a marginal mean improvement (0.7123) and a substantial reduction in variance (0.0164 vs. 0.0239), which we attribute to the position-specific projections stabilizing the training trajectory across seeds. Replacing the path lift with the unified lift (row 3) gives the best mean test AUC (0.7132), again with reduced variance. Composing both modifications (row 4) does not produce further gains and in fact performs slightly worse than either modification in isolation, suggesting that the two degrees of freedom are partially redundant on Cora; we conjecture that the additional parameters of the learnable init interact with the richer unified adjacency structure in a way that regularization at dropout 0.3 cannot fully counter.

Computational analysis

Table 2 reports the empirical cost of the four configurations on Cora, measured on an NVIDIA^® GPU with tools/bench_cost.py. Three effects are visible. First, the learnable init adds 275,136 parameters to the encoder (from 428,544 to 703,680, a 64% increase) because the shared input projection $W^{(k)}$ is replaced by $(k + 1)$ position-specific projections for each $k = 1, 2$; in wall-clock terms a training epoch grows from 28.5 ms to 37.5 ms on the path complex, a 32% overhead. Second, moving from the path lift to the unified lift raises the dim-2 cell count from 38,008 path-cells to 47,717 path- and ring-cells (an extra 9,709 induced cycles of length at most $L = 7$); this is a 26% increase in dim-2 cells and approximately a tripling of lift time, from 22.0 s to 62.8 s. Third, training-epoch overhead from the unified lift is modest ($28.5 \to 33.0$ ms with the deterministic init) because message passing is dominated by dim-0 and dim-1 cells, whose counts are identical across the two lifts.

Table 2. Measured cost of each configuration on Cora. Lift time is one-off preprocessing (building the cell tables and boundary relations). Train epoch is wall-clock time per full-graph training epoch, averaged over 20 epochs after 3 warm-up epochs. Parameters counts learnable parameters in the encoder.

Configuration	Lift time (s)	Train epoch (ms)	Parameters
Path, Deterministic	22.0	28.5	428,544
Path, Learnable	22.0	37.5	703,680
Unified, Deterministic	62.8	33.0	428,544
Unified, Learnable	62.8	43.2	703,680

Asymptotically, enumerating all simple $k$-paths in a graph on $n$ nodes with branching factor $b$ takes time $\mathcal{O}(n \cdot b^k)$ . Adding the ring extractor raises the bound only by $\mathcal{O}(n \cdot b^L)$ for the maximum ring size $L$, which for small $L$ (e.g. $L = 7$ on Cora) is comparable to the path enumeration at $k = 2$. The learnable init adds $\mathcal{O}(k_\text{max}^2 \cdot d \cdot d_\text{in})$ parameters and does not alter the asymptotic cost of message passing.

Discussion

Neither of our modifications is expected to close the gap to specialized link-prediction architectures such as SEAL , NBFNet , or a well-tuned VGAE —those models exploit properties of the link-prediction problem (subgraph enclosure, Bellman–Ford relational paths, bilinear decoders on structural features) that are largely orthogonal to the topological lift studied here. What the ablation does isolate is the marginal effect, within the PCN family, of (i) learning the lift from data and (ii) admitting multiple cell types simultaneously.

A natural limitation of the unified complex is duplication: a 3-cycle $ABC$ is now represented both as a ring-cell and as three path-cells $A{\to}B{\to}C$, $B{\to}C{\to}A$, and $C{\to}A{\to}B$. We do not deduplicate, and we expect this to over-weight triangle structure; exploring learnable gating between cell types—so the model can route messages preferentially through path-cells or ring-cells depending on the task—is a promising direction. Separately, the modest gains observed on Cora may reflect the saturation of AUC on a small, dense citation graph; larger benchmarks such as OGBL-COLLAB and OGBL-PPA, where closed-neighborhood structure varies more widely across node pairs, are a natural next target.

Related work

Higher-order GNNs. Topological deep learning investigates interactions beyond pair-wise adjacencies and has gained significant attention in recent years . introduce MPSN and CWN, message-passing models over simplicial complexes and regular cell complexes, which are provably not less powerful than the 3-WL test. extend CWN to CIN++ by incorporating lower-adjacent messages. propose PCN, which lifts to path complexes and is proven to generalize CWL($k$-IC) with maximum dimension 2. Our work sits strictly within the PCN family and investigates complementary degrees of freedom that the original paper leaves unused.

Link prediction with GNNs. introduce the transductive link-prediction protocol on citation networks with the VGAE model. propose SEAL, which extracts enclosing subgraphs around candidate edges and learns a graph-classification model over them. generalize Bellman–Ford to neural relational path aggregation (NBFNet). These approaches exploit properties of the link-prediction problem itself (subgraph enclosure, path counting) rather than the topological richness of the underlying complex, and our contributions are compatible with any of them at the encoder level.

Path-based graph learning. (pathGCN) learn spatial operators from randomly sampled paths. (PathNN) update node representations based on paths of different lengths. (GSN) encode nodes or edges by counting the occurrences of sub-structures they belong to. Unlike these methods, which operate on top of the standard graph structure, PCN lifts the graph to a genuinely higher-order object; our extensions retain that advantage while widening the set of topological signals available to the model.

Learnable lifts. Most topological GNNs use a fixed, hand-designed lift: cliques of bounded size , induced cycles up to a cutoff , or simple paths of bounded length . A small number of recent works explore lifts that are themselves learned from data; our position-aware initialization can be seen as a minimal instance of this idea, in which the cell type (path vs. ring) is fixed but the mapping from constituent node features to the cell feature is learned.

Conclusion

We have introduced two targeted extensions to Path Complex Networks: a position-aware learnable cell initialization that is strictly more expressive than the deterministic scatter-sum, and a unified path + cellular lift that admits path-cells and ring-cells at a common dimension and fuses them through shared edge boundaries. We prove that the resulting unified isomorphism test U-PWL is at least as powerful as both PWL and CWL($k$-IC), and we empirically ablate both modifications on Cora link prediction. Each modification in isolation yields a small improvement in mean test AUC and a noticeable reduction in seed variance, while composing both does not deliver further gains—suggesting that on this benchmark the two degrees of freedom are partially redundant. Future work includes extending the unified complex to admit clique-cells (simplicial) alongside paths and rings, evaluating on larger OGB link-prediction benchmarks, testing whether the position-aware initialization offers benefits for graph-classification tasks on which PCN is already competitive, and introducing learnable gating between cell types so the model can route messages preferentially through path-cells or ring-cells depending on the task.

Acknowledgments

We thank the Thayer School of Engineering at Dartmouth College for providing computing resources.