能够推荐在线社交网络中用户之间的链接对于用户与志趣相投的个人以及利用社交媒体信息发展业务的平台本身和第三方联系很重要。预测通常基于无监督或监督的学习，通常利用简单而有效的图形拓扑信息，例如普通邻居的数量。但是，我们认为有关个人个人社会结构的更丰富信息可能会带来更好的预测。在本文中，我们建议利用良好的社会认知理论来提高链接预测绩效。根据这些理论，个人平均将自己的社会关系安排在五个同心圆下，以减少亲密关系。我们假设不同圈子中的关系在预测新链接方面具有不同的重要性。为了验证这一主张，我们专注于流行的功能萃取预测算法（既无监督和监督），并将其扩展到包括社交圈的意识。我们验证了这些圆圈感知算法对几个基准测试的预测性能（包括其基线版本以及基于节点的链接和GNN链接预测），利用了两个Twitter数据集，其中包括一个视频游戏玩家和通用用户的社区。我们表明，社会意识通常可以在预测绩效方面有重大改进，击败了Node2Vec和Seal等最新解决方案，而不会增加计算复杂性。最后，我们表明可以使用社交意识来代替针对特定类别用户的分类器（可能是昂贵或不切实际）的。

Link prediction is a key problem for network-structured data. Link prediction heuristics use some score functions, such as common neighbors and Katz index, to measure the likelihood of links. They have obtained wide practical uses due to their simplicity, interpretability, and for some of them, scalability. However, every heuristic has a strong assumption on when two nodes are likely to link, which limits their effectiveness on networks where these assumptions fail. In this regard, a more reasonable way should be learning a suitable heuristic from a given network instead of using predefined ones. By extracting a local subgraph around each target link, we aim to learn a function mapping the subgraph patterns to link existence, thus automatically learning a "heuristic" that suits the current network. In this paper, we study this heuristic learning paradigm for link prediction. First, we develop a novel γ-decaying heuristic theory. The theory unifies a wide range of heuristics in a single framework, and proves that all these heuristics can be well approximated from local subgraphs. Our results show that local subgraphs reserve rich information related to link existence. Second, based on the γ-decaying theory, we propose a new method to learn heuristics from local subgraphs using a graph neural network (GNN). Its experimental results show unprecedented performance, working consistently well on a wide range of problems.

图形嵌入是图形节点到一组向量的转换。良好的嵌入应捕获图形拓扑，节点与节点的关系以及有关图，其子图和节点的其他相关信息。如果实现了这些目标，则嵌入是网络中有意义的，可理解的，可理解的压缩表示形式，可用于其他机器学习工具，例如节点分类，社区检测或链接预测。主要的挑战是，需要确保嵌入很好地描述图形的属性。结果，选择最佳嵌入是一项具有挑战性的任务，并且通常需要领域专家。在本文中，我们在现实世界网络和人为生成的网络上进行了一系列广泛的实验，并使用选定的图嵌入算法进行了一系列的实验。根据这些实验，我们制定了两个一般结论。首先，如果需要在运行实验之前选择一种嵌入算法，则Node2Vec是最佳选择，因为它在我们的测试中表现最好。话虽如此，在所有测试中都没有单一的赢家，此外，大多数嵌入算法都具有应该调整并随机分配的超参数。因此，如果可能的话，我们对从业者的主要建议是生成几个问题的嵌入，然后使用一个通用框架，该框架为无监督的图形嵌入比较提供了工具。该框架（最近在文献中引入并在GitHub存储库中很容易获得）将分歧分数分配给嵌入，以帮助区分好的分数和不良的分数。

Clustering is a fundamental problem in network analysis that finds closely connected groups of nodes and separates them from other nodes in the graph, while link prediction is to predict whether two nodes in a network are likely to have a link. The definition of both naturally determines that clustering must play a positive role in obtaining accurate link prediction tasks. Yet researchers have long ignored or used inappropriate ways to undermine this positive relationship. In this article, We construct a simple but efficient clustering-driven link prediction framework(ClusterLP), with the goal of directly exploiting the cluster structures to obtain connections between nodes as accurately as possible in both undirected graphs and directed graphs. Specifically, we propose that it is easier to establish links between nodes with similar representation vectors and cluster tendencies in undirected graphs, while nodes in a directed graphs can more easily point to nodes similar to their representation vectors and have greater influence in their own cluster. We customized the implementation of ClusterLP for undirected and directed graphs, respectively, and the experimental results using multiple real-world networks on the link prediction task showed that our models is highly competitive with existing baseline models. The code implementation of ClusterLP and baselines we use are available at https://github.com/ZINUX1998/ClusterLP.

本次调查绘制了用于分析社交媒体数据的生成方法的研究状态的广泛的全景照片（Sota）。它填补了空白，因为现有的调查文章在其范围内或被约会。我们包括两个重要方面，目前正在挖掘和建模社交媒体的重要性：动态和网络。社会动态对于了解影响影响或疾病的传播，友谊的形成，友谊的形成等，另一方面，可以捕获各种复杂关系，提供额外的洞察力和识别否则将不会被注意的重要模式。

图表表示学习是一种快速增长的领域，其中一个主要目标是在低维空间中产生有意义的图形表示。已经成功地应用了学习的嵌入式来执行各种预测任务，例如链路预测，节点分类，群集和可视化。图表社区的集体努力提供了数百种方法，但在所有评估指标下没有单一方法擅长，例如预测准确性，运行时间，可扩展性等。该调查旨在通过考虑算法来评估嵌入方法的所有主要类别的图表变体，参数选择，可伸缩性，硬件和软件平台，下游ML任务和多样化数据集。我们使用包含手动特征工程，矩阵分解，浅神经网络和深图卷积网络的分类法组织了图形嵌入技术。我们使用广泛使用的基准图表评估了节点分类，链路预测，群集和可视化任务的这些类别算法。我们在Pytorch几何和DGL库上设计了我们的实验，并在不同的多核CPU和GPU平台上运行实验。我们严格地审查了各种性能指标下嵌入方法的性能，并总结了结果。因此，本文可以作为比较指南，以帮助用户选择最适合其任务的方法。

Graph AutoCododers（GAE）和变分图自动编码器（VGAE）作为链接预测的强大方法出现。他们的表现对社区探测问题的印象不那么令人印象深刻，根据最近和同意的实验评估，它们的表现通常超过了诸如louvain方法之类的简单替代方案。目前尚不清楚可以通过GAE和VGAE改善社区检测的程度，尤其是在没有节点功能的情况下。此外，不确定是否可以在链接预测上同时保留良好的性能。在本文中，我们表明，可以高精度地共同解决这两个任务。为此，我们介绍和理论上研究了一个社区保留的消息传递方案，通过在计算嵌入空间时考虑初始图形结构和基于模块化的先验社区来掺杂我们的GAE和VGAE编码器。我们还提出了新颖的培训和优化策略，包括引入一个模块化的正规器，以补充联合链路预测和社区检测的现有重建损失。我们通过对各种现实世界图的深入实验验证，证明了方法的经验有效性，称为模块化感知的GAE和VGAE。

复杂的网络是代表现实生活系统的图形，这些系统表现出独特的特征，这些特征在纯粹的常规或完全随机的图中未发现。由于基础过程的复杂性，对此类系统的研究至关重要，但具有挑战性。然而，由于大量网络数据的可用性，近几十年来，这项任务变得更加容易。复杂网络中的链接预测旨在估计网络中缺少两个节点之间的链接的可能性。由于数据收集的不完美或仅仅是因为它们尚未出现，因此可能会缺少链接。发现网络数据中实体之间的新关系吸引了研究人员在社会学，计算机科学，物理学和生物学等各个领域的关注。大多数现有研究的重点是无向复杂网络中的链接预测。但是，并非所有现实生活中的系统都可以忠实地表示为无向网络。当使用链接预测算法时，通常会做出这种简化的假设，但不可避免地会导致有关节点之间关系和预测性能中降解的信息的丢失。本文介绍了针对有向网络的明确设计的链接预测方法。它基于相似性范式，该范式最近已证明在无向网络中成功。提出的算法通过在相似性和受欢迎程度上将其建模为不对称性来处理节点关系中的不对称性。鉴于观察到的网络拓扑结构，该算法将隐藏的相似性近似为最短路径距离，并使用边缘权重捕获并取消链接的不对称性和节点的受欢迎程度。在现实生活中评估了所提出的方法，实验结果证明了其在预测各种网络数据类型和大小的丢失链接方面的有效性。

链接预测旨在推断网络/图中的一对节点对之间的链接存在。尽管应用了广泛的应用，但传统链接预测算法的成功受到了三个主要挑战（链接稀疏，节点属性噪声和动态变化）的影响，这些挑战受到许多现实世界网络所面临的。为了应对这些挑战，我们提出了一个上下文化的自我监督学习（CSSL）框架，该框架充分利用了链接预测的结构上下文预测。提出的CSSL框架学习了一个链接编码器，以从配对的节点嵌入中推断链接存在概率，这些嵌入是通过节点属性上的转换构建的。为了生成链接预测的信息节点嵌入，结构上下文预测被用作自我监督的学习任务，以提高链接预测性能。研究了两种类型的结构上下文，即从随机步行和上下文子图收集的上下文节点。 CSSL框架可以以端到端的方式进行训练，并通过通过链接预测和自我监督的学习任务来监督模型参数的学习。提出的CSSL是一个通用且灵活的框架，因为它可以同时处理属性和非属性网络，并且在跨性和归纳性链接预测设置下进行操作。对七个现实世界基准网络进行的广泛实验和消融研究表明，在转化和归纳性环境下，在不同类型的网络上，提出的基于自学的链接链路预测算法优于最先进的基线。拟议的CSSL还可以从大规模网络上的节点属性噪声和可扩展性方面产生竞争性能。

Prediction tasks over nodes and edges in networks require careful effort in engineering features used by learning algorithms. Recent research in the broader field of representation learning has led to significant progress in automating prediction by learning the features themselves. However, present feature learning approaches are not expressive enough to capture the diversity of connectivity patterns observed in networks.Here we propose node2vec, an algorithmic framework for learning continuous feature representations for nodes in networks. In node2vec, we learn a mapping of nodes to a low-dimensional space of features that maximizes the likelihood of preserving network neighborhoods of nodes. We define a flexible notion of a node's network neighborhood and design a biased random walk procedure, which efficiently explores diverse neighborhoods. Our algorithm generalizes prior work which is based on rigid notions of network neighborhoods, and we argue that the added flexibility in exploring neighborhoods is the key to learning richer representations.We demonstrate the efficacy of node2vec over existing state-ofthe-art techniques on multi-label classification and link prediction in several real-world networks from diverse domains. Taken together, our work represents a new way for efficiently learning stateof-the-art task-independent representations in complex networks.

Pre-publication draft of a book to be published byMorgan & Claypool publishers. Unedited version released with permission. All relevant copyrights held by the author and publisher extend to this pre-publication draft.

Graph classification is an important area in both modern research and industry. Multiple applications, especially in chemistry and novel drug discovery, encourage rapid development of machine learning models in this area. To keep up with the pace of new research, proper experimental design, fair evaluation, and independent benchmarks are essential. Design of strong baselines is an indispensable element of such works. In this thesis, we explore multiple approaches to graph classification. We focus on Graph Neural Networks (GNNs), which emerged as a de facto standard deep learning technique for graph representation learning. Classical approaches, such as graph descriptors and molecular fingerprints, are also addressed. We design fair evaluation experimental protocol and choose proper datasets collection. This allows us to perform numerous experiments and rigorously analyze modern approaches. We arrive to many conclusions, which shed new light on performance and quality of novel algorithms. We investigate application of Jumping Knowledge GNN architecture to graph classification, which proves to be an efficient tool for improving base graph neural network architectures. Multiple improvements to baseline models are also proposed and experimentally verified, which constitutes an important contribution to the field of fair model comparison.

A key challenge in social network analysis is understanding the position, or stance, of people in the graph on a large set of topics. While past work has modeled (dis)agreement in social networks using signed graphs, these approaches have not modeled agreement patterns across a range of correlated topics. For instance, disagreement on one topic may make disagreement(or agreement) more likely for related topics. We propose the Stance Embeddings Model(SEM), which jointly learns embeddings for each user and topic in signed social graphs with distinct edge types for each topic. By jointly learning user and topic embeddings, SEM is able to perform cold-start topic stance detection, predicting the stance of a user on topics for which we have not observed their engagement. We demonstrate the effectiveness of SEM using two large-scale Twitter signed graph datasets we open-source. One dataset, TwitterSG, labels (dis)agreements using engagements between users via tweets to derive topic-informed, signed edges. The other, BirdwatchSG, leverages community reports on misinformation and misleading content. On TwitterSG and BirdwatchSG, SEM shows a 39% and 26% error reduction respectively against strong baselines.

在过去的二十年中，我们目睹了以图形或网络形式构建的有价值的大数据的大幅增长。为了将传统的机器学习和数据分析技术应用于此类数据，有必要将图形转换为基于矢量的表示，以保留图形最重要的结构属性。为此，文献中已经提出了大量的图形嵌入方法。它们中的大多数产生了适用于各种应用的通用嵌入，例如节点聚类，节点分类，图形可视化和链接预测。在本文中，我们提出了两个新的图形嵌入算法，这些算法是基于专门为节点分类问题设计的随机步道。已设计算法的随机步行采样策略旨在特别注意集线器 - 高度节点，这些节点在大规模图中具有最关键的作用。通过分析对现实世界网络嵌入的三种分类算法的分类性能，对所提出的方法进行实验评估。获得的结果表明，与当前最流行的随机步行方法相比，我们的方法可大大提高所检查分类器的预测能力（NODE2VEC）。

图表表示学习已经成为许多情景中的无处不在的组成部分，从社会网络分析到智能电网的能量预测。在几个应用程序中，确保关于某些受保护属性的节点（或图形）表示的公平对其正确部署至关重要。然而，图表深度学习的公平仍然在探索，很少有解决方案。特别地，在若干真实世界图（即同声源性）上相似节点对簇的趋势可以显着恶化这些程序的公平性。在本文中，我们提出了一种新颖的偏见边缘辍学算法（Fairdrop）来反击精神剧并改善图形表示学习中的公平性。 Fairdrop可以在许多现有算法上轻松插入，具有高效，适应性，并且可以与其他公平诱导的解决方案结合。在描述了一般算法之后，我们在两个基准任务中展示其应用，具体地，作为用于生产节点嵌入的随机步道模型，以及用于链路预测的图形卷积网络。我们证明，所提出的算法可以成功地改善所有型号的公平，直到精度小或可忽略的降低，并与现有的最先进的解决方案相比。在一个消融研究中，我们证明我们的算法可以灵活地在偏置公平性和无偏见的边缘辍学之间插入。此外，为了更好地评估增益，我们提出了一种新的二元组定义，以测量与基于组的公平度量配对时的链路预测任务的偏差。特别是，我们扩展了用于测量节点嵌入的偏差的指标，以考虑图形结构。

近年来，对图表的研究受到了极大的关注。但是，到目前为止，大多数研究都集中在单层图的嵌入上。涉及多层结构的表示问题问题的少数研究取决于以下强烈的假设：层间链接是已知的，这限制了可能的应用范围。在这里，我们提出了多层，这是允许嵌入多重网络的图形算法的概括。我们表明，多层能够重建层内和层间连接性，超过了图形，该图是为简单图形而设计的。接下来，通过全面的实验分析，我们还以简单和多重网络中的嵌入性能阐明，表明图的密度或链接的随机性都会强烈影响嵌入的质量。

在本文中，我们提出了一种方法，用于预测社交媒体对等体之间的信任链接，其中一个是在多识别信任建模的人工智能面积。特别是，我们提出了一种数据驱动的多面信任信任建模，该信任建模包括许多不同的特征以进行全面分析。我们专注于展示类似用户的聚类如何实现关键新功能：支持更个性化的，从而为用户提供更准确的预测。在信任感知项目推荐任务中说明，我们在大yelp数据集的上下文中评估所提出的框架。然后，我们讨论如何提高社交媒体的可信关系的检测可以帮助在最近爆发的社交网络环境中支持在线用户的违法行为和谣言的传播。我们的结论是关于一个特别易受资助的用户基础，老年人的反思，以说明关于用户组的推理价值，期望通过通过数据分析获得的洞察力集成已知偏好的一些未来方向。

近年来，基于Weisfeiler-Leman算法的算法和神经架构，是一个众所周知的Graph同构问题的启发式问题，它成为具有图形和关系数据的机器学习的强大工具。在这里，我们全面概述了机器学习设置中的算法的使用，专注于监督的制度。我们讨论了理论背景，展示了如何将其用于监督的图形和节点表示学习，讨论最近的扩展，并概述算法的连接（置换 - ）方面的神经结构。此外，我们概述了当前的应用和未来方向，以刺激进一步的研究。

Inferring missing links or detecting spurious ones based on observed graphs, known as link prediction, is a long-standing challenge in graph data analysis. With the recent advances in deep learning, graph neural networks have been used for link prediction and have achieved state-of-the-art performance. Nevertheless, existing methods developed for this purpose are typically discriminative, computing features of local subgraphs around two neighboring nodes and predicting potential links between them from the perspective of subgraph classification. In this formalism, the selection of enclosing subgraphs and heuristic structural features for subgraph classification significantly affects the performance of the methods. To overcome this limitation, this paper proposes a novel and radically different link prediction algorithm based on the network reconstruction theory, called GraphLP. Instead of sampling positive and negative links and heuristically computing the features of their enclosing subgraphs, GraphLP utilizes the feature learning ability of deep-learning models to automatically extract the structural patterns of graphs for link prediction under the assumption that real-world graphs are not locally isolated. Moreover, GraphLP explores high-order connectivity patterns to utilize the hierarchical organizational structures of graphs for link prediction. Our experimental results on all common benchmark datasets from different applications demonstrate that the proposed method consistently outperforms other state-of-the-art methods. Unlike the discriminative neural network models used for link prediction, GraphLP is generative, which provides a new paradigm for neural-network-based link prediction.

链接预测是一项重要的任务，在各个域中具有广泛的应用程序。但是，大多数现有的链接预测方法都假定给定的图遵循同质的假设，并设计基于相似性的启发式方法或表示学习方法来预测链接。但是，许多现实世界图是异性图，同义假设不存在，这挑战了现有的链接预测方法。通常，在异性图中，有许多引起链接形成的潜在因素，并且两个链接的节点在一个或两个因素中往往相似，但在其他因素中可能是不同的，导致总体相似性较低。因此，一种方法是学习每个节点的分离表示形式，每个矢量捕获一个因子上的节点的潜在表示，这铺平了一种方法来模拟异性图中的链接形成，从而导致更好的节点表示学习和链接预测性能。但是，对此的工作非常有限。因此，在本文中，我们研究了一个新的问题，该问题是在异性图上进行链接预测的分离表示学习。我们提出了一种新颖的框架分解，可以通过建模链接形成并执行感知因素的消息来学习以促进链接预测来学习解开的表示形式。在13个现实世界数据集上进行的广泛实验证明了Disenlink对异性恋和血友病图的链接预测的有效性。我们的代码可从https://github.com/sjz5202/disenlink获得