Implicit graph neural networks have gained popularity in recent years as they
capture long-range dependencies while improving predictive performance in
static graphs. Despite the tussle between performance degradation due to the
oversmoothing of learned embeddings and long-range dependency being more
pronounced in dynamic graphs, as features are aggregated both across
neighborhood and time, no prior work has proposed an implicit graph neural
model in a dynamic setting. In this paper, we present Implicit Dynamic Graph
Neural Network (IDGNN) a novel implicit neural network for dynamic graphs which
is the first of its kind. A key characteristic of IDGNN is that it demonstrably
is well-posed, i.e., it is theoretically guaranteed to have a fixed-point
representation. We then demonstrate that the standard iterative algorithm often
used to train implicit models is computationally expensive in our dynamic
setting as it involves computing gradients, which themselves have to be
estimated in an iterative manner. To overcome this, we pose an equivalent
bilevel optimization problem and propose an efficient single-loop training
algorithm that avoids iterative computation by maintaining moving averages of
key components of the gradients. We conduct extensive experiments on real-world
datasets on both classification and regression tasks to demonstrate the
superiority of our approach over the state-of-the-art baselines. We also
demonstrate that our bi-level optimization framework maintains the performance
of the expensive iterative algorithm while obtaining up to \textbf{1600x}
speed-up.

Implicit Dynamic Graph Neural Network (IDGNN) 是一种针对动态图的新型隐式神经网络模型，通过提出一个等价的双层优化问题和一种高效的单循环训练算法来克服计算上的困难，以在分类和回归任务中展现出优于现有模型的性能，并在性能保持的同时获得高达 1600 倍的加速。

高效有效的隐式动态图神经网络

Efficient and Effective Implicit Dynamic Graph Neural Network

Implicit graph neural networks (GNNs) have emerged as a potential approach to
enable GNNs to capture long-range dependencies effectively. However, poorly
designed implicit GNN layers can experience over-smoothing or may have limited
adaptability to learn data geometry, potentially hindering their performance in
graph learning problems. To address these issues, we introduce a geometric
framework to design implicit graph diffusion layers based on a parameterized
graph Laplacian operator. Our framework allows learning the geometry of vertex
and edge spaces, as well as the graph gradient operator from data. We further
show how implicit GNN layers can be viewed as the fixed-point solution of a
Dirichlet energy minimization problem and give conditions under which it may
suffer from over-smoothing. To overcome the over-smoothing problem, we design
our implicit graph diffusion layer as the solution of a Dirichlet energy
minimization problem with constraints on vertex features, enabling it to trade
off smoothing with the preservation of node feature information. With an
appropriate hyperparameter set to be larger than the largest eigenvalue of the
parameterized graph Laplacian, our framework guarantees a unique equilibrium
and quick convergence. Our models demonstrate better performance than leading
implicit and explicit GNNs on benchmark datasets for node and graph
classification tasks, with substantial accuracy improvements observed for some
datasets.

设计基于参数化图拉普拉斯算子的隐式图扩散层，从而在节点和图分类任务中展现了强化的性能，通过减少超平滑问题，权衡平滑和节点特征信息的保持。

基于约束狄利克雷能量最小化的隐式图神经扩散

Implicit Graph Neural Diffusion Based on Constrained Dirichlet Energy  Minimization

Recently, implicit graph neural networks (GNNs) have been proposed to capture
long-range dependencies in underlying graphs. In this paper, we introduce and
justify two weaknesses of implicit GNNs: the constrained expressiveness due to
their limited effective range for capturing long-range dependencies, and their
lack of ability to capture multiscale information on graphs at multiple
resolutions. To show the limited effective range of previous implicit GNNs, We
first provide a theoretical analysis and point out the intrinsic relationship
between the effective range and the convergence of iterative equations used in
these models. To mitigate the mentioned weaknesses, we propose a multiscale
graph neural network with implicit layers (MGNNI) which is able to model
multiscale structures on graphs and has an expanded effective range for
capturing long-range dependencies. We conduct comprehensive experiments for
both node classification and graph classification to show that MGNNI
outperforms representative baselines and has a better ability for multiscale
modeling and capturing of long-range dependencies.

本文介绍和证明了隐式图神经网络存在的两个弱点：他们的限制表达能力由于他们对捕获长程依赖性的有效范围有限以及他们无法在多个分辨率上对图进行多尺度信息建模。为了缓解这些弱点，我们提出了一种带有隐式层次的多尺度图神经网络 (MGNNI)，它能够模拟图的多尺度结构，具有更广泛的有效范围，能够捕获长程依赖性，并且在节点分类和图分类方面，我们进行了全面的实验来表明 MGNNI 优于代表性基准，并具有更好的多尺度建模和捕获长程依赖性的能力。

MGNNI: 带隐式层的多尺度图神经网络

MGNNI: Multiscale Graph Neural Networks with Implicit Layers

Graph Neural Networks (GNNs) are widely used deep learning models that learn
meaningful representations from graph-structured data. Due to the finite nature
of the underlying recurrent structure, current GNN methods may struggle to
capture long-range dependencies in underlying graphs. To overcome this
difficulty, we propose a graph learning framework, called Implicit Graph Neural
Networks (IGNN), where predictions are based on the solution of a fixed-point
equilibrium equation involving implicitly defined "state" vectors. We use the
Perron-Frobenius theory to derive sufficient conditions that ensure
well-posedness of the framework. Leveraging implicit differentiation, we derive
a tractable projected gradient descent method to train the framework.
Experiments on a comprehensive range of tasks show that IGNNs consistently
capture long-range dependencies and outperform the state-of-the-art GNN models.

本文提出了一种名为 “Implicit Graph Neural Networks（IGNN）” 的图学习框架，其利用 Perron-Frobenius 理论来确保该框架的良好性，并利用隐式微分得到一种可行的投影梯度下降法来训练该框架，实验证明 IGNN 可以稳定捕捉长程依赖并优于现有的 GNN 模型。