Real-world graphs exhibit increasing heterophily, where nodes no longer tend
to be connected to nodes with the same label, challenging the homophily
assumption of classical graph neural networks (GNNs) and impeding their
performance. Intriguingly, we observe that certain high-order information on
heterophilous data exhibits high homophily, which motivates us to involve
high-order information in node representation learning. However, common
practices in GNNs to acquire high-order information mainly through increasing
model depth and altering message-passing mechanisms, which, albeit effective to
a certain extent, suffer from three shortcomings: 1) over-smoothing due to
excessive model depth and propagation times; 2) high-order information is not
fully utilized; 3) low computational efficiency. In this regard, we design a
similarity-based path sampling strategy to capture smooth paths containing
high-order homophily. Then we propose a lightweight model based on multi-layer
perceptrons (MLP), named PathMLP, which can encode messages carried by paths
via simple transformation and concatenation operations, and effectively learn
node representations in heterophilous graphs through adaptive path aggregation.
Extensive experiments demonstrate that our method outperforms baselines on 16
out of 20 datasets, underlining its effectiveness and superiority in
alleviating the heterophily problem. In addition, our method is immune to
over-smoothing and has high computational efficiency.

通过设计一种基于相似度的路径采样策略来捕获包含高阶同质性的连续路径以及提出一种名为 PathMLP 的轻量级模型来适应路径聚合，从而在异质性图形中有效地学习节点表示，并证明了其在缓解异质性问题方面的有效性和优越性。

PathMLP: 向高阶同质化之路平稳前进

PathMLP: Smooth Path Towards High-order Homophily

Hypergraph neural networks (HGNN) have recently become attractive and
received significant attention due to their excellent performance in various
domains. However, most existing HGNNs rely on first-order approximations of
hypergraph connectivity patterns, which ignores important high-order
information. To address this issue, we propose a novel adjacency-tensor-based
Tensorized Hypergraph Neural Network (THNN). THNN is a faithful hypergraph
modeling framework through high-order outer product feature message passing and
is a natural tensor extension of the adjacency-matrix-based graph neural
networks. The proposed THNN is equivalent to an high-order polynomial
regression scheme, which enable THNN with the ability to efficiently extract
high-order information from uniform hypergraphs. Moreover, in consideration of
the exponential complexity of directly processing high-order outer product
features, we propose using a partially symmetric CP decomposition approach to
reduce model complexity to a linear degree. Additionally, we propose two simple
yet effective extensions of our method for non-uniform hypergraphs commonly
found in real-world applications. Results from experiments on two widely used
hypergraph datasets for 3-D visual object classification show the promising
performance of the proposed THNN.

提出了一种基于张量的高阶超图神经网络模型，它利用高阶外积特征传递实现了对高阶信息的有效提取，并通过部分对称 CP 分解方法降低了模型复杂度；在两个三维视觉对象分类数据集上进行的实验结果表明了其性能优越性。

张量化超图神经网络

Tensorized Hypergraph Neural Networks

Graph embedding methods including traditional shallow models and deep Graph
Neural Networks (GNNs) have led to promising applications in recommendation.
Nevertheless, shallow models especially random-walk-based algorithms fail to
adequately exploit neighbor proximity in sampled subgraphs or sequences due to
their optimization paradigm. GNN-based algorithms suffer from the insufficient
utilization of high-order information and easily cause over-smoothing problems
when stacking too much layers, which may deteriorate the recommendations of
low-degree (long-tail) items, limiting the expressiveness and scalability. In
this paper, we propose a novel framework SAC, namely Spatial Autoregressive
Coding, to solve the above problems in a unified way. To adequately leverage
neighbor proximity and high-order information, we design a novel spatial
autoregressive paradigm. Specifically, we first randomly mask multi-hop
neighbors and embed the target node by integrating all other surrounding
neighbors with an explicit multi-hop attention. Then we reinforce the model to
learn a neighbor-predictive coding for the target node by contrasting the
coding and the masked neighbors' embedding, equipped with a new hard negative
sampling strategy. To learn the minimal sufficient representation for the
target-to-neighbor prediction task and remove the redundancy of neighbors, we
devise Neighbor Information Bottleneck by maximizing the mutual information
between target predictive coding and the masked neighbors' embedding, and
simultaneously constraining those between the coding and surrounding neighbors'
embedding. Experimental results on both public recommendation datasets and a
real scenario web-scale dataset Douyin-Friend-Recommendation demonstrate the
superiority of SAC compared with state-of-the-art methods.

本文提出了一种名为 SAC 的新型框架，它采用了一种新的空间自回归范式来充分利用邻居的接近性和高阶信息，同时还提出了邻居信息瓶颈来学习目标节点到邻居的预测任务的最小充分表示，并消除邻居的冗余，实验结果表明，在公共推荐数据集和某真实情境下的大型数据集 Douyin-Friend-Recommendation 上，SAC 方法优于现有的最先进的方法。