随着大数据时代的到来,海量、高维、不规则等数据特征为信息处理带来新的挑战。图上信号处理研究离散不规则域上的信号与信息处理理论和方法,可以为大数据时代的信息处理提供新思路和新解决方案。降维是解决高维问题的关键途径,重建方法是逆问题求解的核心工具,它们在图上信号处理中具有重要作用。目前,图上相关研究仍处于起步阶段。本文研究图上信号的粗化、图上信号的采样和重建、图上布尔型信号的重建等三个具体的降维和重建问题,主要创新工作如下:1.研究图上信号粗化问题,提出图上信号粗化算法的评价指标——谱差异度,可度量任意两图上信号的频域相似性。为解决已知粗化图的信号粗化问题,提出谱装箱法,并证明该方法是谱差异度最小意义下的最优方法。基于谱装箱法设计图上信号的接连粗化方案。针对当前粗化方法中图与信号被割裂的问题,提出最小化谱差异度的图上信号联合粗化方法。在方法的设计中证明了新图的图谱应为原图谱的子集,并使用ADMM与流形上优化方法由图上信号谱获得图上信号。实验验证了本文提出的方法可以达到粗化前后的图上信号在节点域表示和频域表示中均相似的目标;对比实验表明所提方法更好地保持了粗化前后图上信号频域表示的相似性。2.研究图上信号的采样和重建问题,指出该问题与时域非规则采样的相似性。借鉴时域非规则采样的重建方案,提出两种图上带限信号重建方法IPR和IWR。实验表明,两种方法在精确实现或近似实现的情况下,在随机网络和真实网络中的收敛速度均优于现有方案。3.以一个特例研究图上布尔型信号重建问题,该特例对应有向社交网络中的Sybil检测问题。提出一类可定制的图划分度量,它是模块度的一种推广;设计针对该度量的优化方案;提出有向社交网络中的Sybil检测方法。实验验证了该方法的有效性,实现了低虚警、无漏报;对比实验表明所提方法明显优于当前无向网络中效果最好的算法。该研究是首个针对有向社交网络中Sybil检测问题的研究,可应用于社交网络中的僵尸账号发现和水军检测。