Exploring Unknown Social Networks for Discovering Hidden Nodes

• URL: http://arxiv.org/abs/2501.12571v2
• Date: Mon, 28 Apr 2025 06:26:01 GMT
• Title: Exploring Unknown Social Networks for Discovering Hidden Nodes
• Authors: Sho Tsugawa, Hiroyuki Ohsaki,
• Abstract summary: We tackle the challenge of discovering hidden nodes in unknown social networks by employing a graph exploration framework grounded in machine learning.<n>Our results show that our graph exploration strategies discover hidden nodes with an efficiency comparable to that when the graph structure is known.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we address the challenge of discovering hidden nodes in unknown social networks, formulating three types of hidden-node discovery problems, namely, Sybil-node discovery, peripheral-node discovery, and influencer discovery. We tackle these problems by employing a graph exploration framework grounded in machine learning. Leveraging the structure of the subgraph gradually obtained from graph exploration, we construct prediction models to identify target hidden nodes in unknown social graphs. Through empirical investigations of real social graphs, we investigate the efficiency of graph exploration strategies in uncovering hidden nodes. Our results show that our graph exploration strategies discover hidden nodes with an efficiency comparable to that when the graph structure is known. Specifically, the query cost of discovering 10% of the hidden nodes is at most only 1.2 times that when the topology is known, and the query-cost multiplier for discovering 90% of the hidden nodes is at most only 1.4. Furthermore, our results suggest that using node embeddings, which are low-dimensional vector representations of nodes, for hidden-node discovery is a double-edged sword: it is effective in certain scenarios but sometimes degrades the efficiency of node discovery. Guided by this observation, we examine the effectiveness of using a bandit algorithm to combine the prediction models that use node embeddings with those that do not, and our analysis shows that the bandit-based graph exploration strategy achieves efficient node discovery across a wide array of settings.

Related papers

• Graph-Skeleton: ~1% Nodes are Sufficient to Represent Billion-Scale Graph [11.661431088477329]
  We propose a novel Graph-Skeleton1 model, which properly fetches the background nodes, and further condenses the semantic and topological information of background nodes within similar target-background local structures. In particular, for MAG240M dataset with 0.24 billion nodes, our generated skeleton graph achieves highly comparable performance while only containing 1.8% nodes of the original graph.
  arXiv  Detail & Related papers  (2024-02-14T20:33:11Z)
• Multitask Active Learning for Graph Anomaly Detection [48.690169078479116]
  We propose a novel MultItask acTIve Graph Anomaly deTEction framework, namely MITIGATE. By coupling node classification tasks, MITIGATE obtains the capability to detect out-of-distribution nodes without known anomalies. Empirical studies on four datasets demonstrate that MITIGATE significantly outperforms the state-of-the-art methods for anomaly detection.
  arXiv  Detail & Related papers  (2024-01-24T03:43:45Z)
• BOURNE: Bootstrapped Self-supervised Learning Framework for Unified Graph Anomaly Detection [50.26074811655596]
  We propose a novel unified graph anomaly detection framework based on bootstrapped self-supervised learning (named BOURNE) By swapping the context embeddings between nodes and edges, we enable the mutual detection of node and edge anomalies. BOURNE can eliminate the need for negative sampling, thereby enhancing its efficiency in handling large graphs.
  arXiv  Detail & Related papers  (2023-07-28T00:44:57Z)
• Robust Knowledge Adaptation for Dynamic Graph Neural Networks [61.8505228728726]
  We propose Ada-DyGNN: a robust knowledge Adaptation framework via reinforcement learning for Dynamic Graph Neural Networks. Our approach constitutes the first attempt to explore robust knowledge adaptation via reinforcement learning. Experiments on three benchmark datasets demonstrate that Ada-DyGNN achieves the state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-07-22T02:06:53Z)
• Deep Fraud Detection on Non-attributed Graph [61.636677596161235]
  Graph Neural Networks (GNNs) have shown solid performance on fraud detection. labeled data is scarce in large-scale industrial problems, especially for fraud detection. We propose a novel graph pre-training strategy to leverage more unlabeled data.
  arXiv  Detail & Related papers  (2021-10-04T03:42:09Z)
• Detecting Communities from Heterogeneous Graphs: A Context Path-based Graph Neural Network Model [23.525079144108567]
  We build a Context Path-based Graph Neural Network (CP-GNN) model. It embeds the high-order relationship between nodes into the node embedding. It outperforms the state-of-the-art community detection methods.
  arXiv  Detail & Related papers  (2021-09-05T12:28:00Z)
• Node2Seq: Towards Trainable Convolutions in Graph Neural Networks [59.378148590027735]
  We propose a graph network layer, known as Node2Seq, to learn node embeddings with explicitly trainable weights for different neighboring nodes. For a target node, our method sorts its neighboring nodes via attention mechanism and then employs 1D convolutional neural networks (CNNs) to enable explicit weights for information aggregation. In addition, we propose to incorporate non-local information for feature learning in an adaptive manner based on the attention scores.
  arXiv  Detail & Related papers  (2021-01-06T03:05:37Z)
• Integrating Network Embedding and Community Outlier Detection via Multiclass Graph Description [15.679313861083239]
  We propose a novel unsupervised graph embedding approach (called DMGD) which integrates outlier and community detection with node embedding. We show the theoretical bounds on the number of outliers detected by DMGD. Our formulation boils down to an interesting minimax game between the outliers, community assignments and the node embedding function.
  arXiv  Detail & Related papers  (2020-07-20T16:21:07Z)
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs [54.13919050090926]
  We propose an end-to-end structural temporal Graph Neural Network model for detecting anomalous edges in dynamic graphs. In particular, we first extract the $h$-hop enclosing subgraph centered on the target edge and propose the node labeling function to identify the role of each node in the subgraph. Based on the extracted features, we utilize Gated recurrent units (GRUs) to capture the temporal information for anomaly detection.
  arXiv  Detail & Related papers  (2020-05-15T09:17:08Z)
• Adversarial Attack on Community Detection by Hiding Individuals [68.76889102470203]
  We focus on black-box attack and aim to hide targeted individuals from the detection of deep graph community detection models. We propose an iterative learning framework that takes turns to update two modules: one working as the constrained graph generator and the other as the surrogate community detection model.
  arXiv  Detail & Related papers  (2020-01-22T09:50:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.